A Clean DP Solution from beginning of the string


  • 0
    H

    Instead of start the loop from end of the string, we can also start from the beginning. It can be more intuitive. The explanation is included in the comments.

    public int numDecodings(String s) {
            int n = s.length();
            if (n==0) return 0;
            int[] dp = new int[n+1];
            dp[0]=1;
            
            for (int i=1;i<=n;i++)
            {
                if (s.charAt(i-1)!='0') dp[i] +=dp[i-1];//if the current digit is non '0', we can encode this digit
                if (i>1 && s.charAt(i-2)!='0' && ((s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0')<=26)) dp[i]+=dp[i-2];//if the previous digit is not '0', and combine it with the current digit is less than or equal to 26, we can encode these two digits together
            }
            return dp[n];
        }
    

Log in to reply
 

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