1ms DP Java Solution!


  • 0
        public int numDecodings(String s) {
            if (s == null || s.length() == 0) return 0;
            if (s.charAt(0) == '0') return 0;
            int n = s.length();
            if (n == 1) return 1;
            int[] dp = new int[n];
            dp[0] = 1;
            if (s.charAt(1) == '0') {
                if (s.charAt(0) - '0' > 2) return 0;
                else dp[1] = 1;
            } else {
                if (s.charAt(0) - '0' > 2) dp[1] = 1;
                else if (s.charAt(0) == '2' && s.charAt(1) - '0' > 6) dp[1] = 1;
                else if (s.charAt(0) == '2' && s.charAt(1) - '0' <= 6) dp[1] = 2;
                else dp[1] = 2;
            }
            for (int i = 2; i < n; i++) {
                char c = s.charAt(i);
                if (c == '0') {
                    if (s.charAt(i - 1) - '0' > 2 || s.charAt(i - 1) == '0') return 0;
                    else dp[i] = dp[i - 2];
                } else {
                    if (s.charAt(i - 1) - '0' > 2) dp[i] = dp[i - 1];
                    else if (s.charAt(i - 1) == '2') {
                        if (c - '0' > 6) dp[i] = dp[i - 1];
                        else dp[i] = dp[i - 1] + dp[i - 2];
                    } else if (s.charAt(i - 1) == '1') dp[i] = dp[i - 1] + dp[i - 2];
                    else dp[i] = dp[i - 1];
                }
            }
            return dp[n - 1];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.