DP Solution (Java) for reference


  • 194
    M
    public class Solution {
        public int numDecodings(String s) {
            int n = s.length();
            if (n == 0) return 0;
            
            int[] memo = new int[n+1];
            memo[n]  = 1;
            memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;
            
            for (int i = n - 2; i >= 0; i--)
                if (s.charAt(i) == '0') continue;
                else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];
            
            return memo[0];
        }
    }

  • 34
    S

    Thanks for your post. However it would be better to share solution with elaborating thoughts. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info. Take a look at good sharing example


  • 1
    M

    elegant code


  • 0
    B

    Very elegant solution. Thank you.


  • 0
    R

    Could you explain why you use memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0; it confused me. Thank you.


  • -2
    R
    This post is deleted!

  • 0
    G

    There is no need to LOL even if you use less memory.


  • 7
    Y

    if the last char of the String is '0'. it means there is no way to use it alone as a code. it has to be a part of another code. If the last char is not '0', let's say it's '5', the there is 1 way to use this number as a code


  • 0
    L

    what if that char is 'a ', if there any chance we can use like regular expression for that?


  • 6
    A

    This is a great solution, wonder how you came up with this idea.


  • 0
    L

    Such a great solution. The most beautiful part of the algorithm is that it covers edge cases without additional if_else :)


  • 0
    B
    This post is deleted!

  • 1
    M

    Could you explain why should scan from end to start instead of scanning from start to end? Because I tried your idea but scan from start to end and that doesn't pass the test case of "10", I couldn't figure out why?


  • 1
    L

    I have the same question. when scan from start to end and get WA if the case is "10".


  • 0
    A

    Because s[i+1] is ' 0' or not will influence how to use s[i]


  • 0
    A

    What a brilliant solution,with using minimal if else statements. Thank you for sharing :)


  • 0
    H
    This post is deleted!

  • 3
    F

    I have the same idea, but the processing for memo[n-1] is not necessary

        if (s.empty()) return 0;
    	vector<int> dp(s.size() + 1, 0);
    	dp[s.size()] = 1;
    
    	for (int i = s.size() - 1; i >= 0; i--) {
    		if (s[i] == '0') { dp[i] = 0; continue; }
    		dp[i] = dp[i + 1];
    		if (i < s.size() - 1 && (s[i] == '1' || (s[i]=='2' && s[i + 1] < '7'))) {
    			dp[i] += dp[i + 2];
    		}
    	}
    	return dp[0];

  • 0
    L

    Because this is bottom up DP, memo[0] is the final result.


  • 1
    Z

    doing dp from tail to head. great!
    memo[i] means ways of decoding for substring(i, end).
    at a certain point i, if the char is '0' then it must be combine with char i-1,


Log in to reply
 

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