DP Java solution


  • 0
    D

    It's easier to do DP backwards (from the end of the string to the start) because any string starts with an zero will have zero way of decoding.

    public class Solution {
        public int numDecodings(String s) {
            int len = s.length();
            if (len == 0) {
                return 0;
            }
            
            // convert to int array
            // return 0 if any non-numerical char is found
            int[] A = new int[len];
            for (int i = 0; i < len; i++) {
                int digit = s.charAt(i) - '0';
                if (digit > 9 || digit < 0) {
                    return 0;
                }
                A[i] = digit;
            }
            
            int[] dp = new int[len + 1];
            dp[len] = 1;
            dp[len - 1] = (A[len - 1] == 0) ? 0 : 1;
            for (int i = len - 2; i >= 0; i--) {
                if (A[i] == 0) {
                    dp[i] = 0;
                }
                else {
                    dp[i] = (A[i] * 10 + A[i + 1] <= 26) ? dp[i + 2] + dp[i + 1] : dp[i + 1];
                }
            }
            
            return dp[0];
        }
    }

Log in to reply
 

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