Java DP Solution O(n) time and space, Some Explanations


  • 8

    Take "1*" as an example. It can be "11"-"19". You can read it into "A" and "A" to "A" and "I" or you can treat it as a two digit number as "K" to "S". That is the way you decode the code.
    So if you treat the current character s.charAt(i) as a single character, the dp result of the index i should be the number of choices of current character times dp[i-1]. If you put the s.charAt(i) together with s.charAt(i-1) as a two digit number (if possible, something like "29" is not a possible pair), dp[i] should add the choices of the current pair times dp[i-2]. That is basic thinking of dp for this problem. Then what should be done is to find what kind of pairs or single numbers are valid. Like a single "0" is not valid, and there is no answer for something like "30".
    Just think about the different conditions carefully.

    public int numDecodings(String s) {
        int len = s.length();
        int mod = 1000000007;
        long [] dp = new long[len + 1];
        dp[0] = 1;
        if (s.charAt(0) == '0') return 0;
        if (s.charAt(0) == '*'){
            dp[1] = 9;
        }
        else{
            dp[1] = 1;
        }
        for (int i = 2; i<=len; i++) { // i-1 the index of current character in s. 
            if (s.charAt(i-1) == '0') {
                if (s.charAt(i-2) == '1' || s.charAt(i -2) == '2') {
                    dp[i] = dp[i-2];
                }
                else if(s.charAt(i-2) == '*'){
                    dp[i] = 2*dp[i-2];
                }
                else {
                    return 0;
                }
            }
            else if(s.charAt(i-1) >= '1' && s.charAt(i-1) <= '9') {
                dp[i] = dp[i-1];
                if (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6') ){
                    dp[i] = (dp[i] + dp[i-2]) % mod;
                }
                else if (s.charAt(i-2) == '*') {
                    if (s.charAt (i-1) <= '6') {
                        dp[i] = (dp[i] + dp[i-2] * 2) % mod;
                    }
                    else {
                        dp[i] = (dp[i] + dp[i-2]) % mod;
                    }
                }
            }
            else { //s.charAt(i-1) == '*'
                dp[i] = (9*dp[i-1]) % mod;
                if ( s.charAt(i-2) == '1' ){ // 11 - 19
                    dp[i] = ( dp[i] + 9 * dp[i-2] ) % mod;
                }
                else if (s.charAt(i-2) == '2') { // 21 - 26
                    dp[i] = ( dp[i] + 6 * dp[i-2] ) % mod;
                }
                else if (s.charAt(i - 2) == '*') {
                    dp[i] = ( dp[i] + 15 * dp[i-2] ) % mod;
                }
            }
        }
        return (int)dp[len];
    }

  • 0
    K

    Similar ideas in Python

    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            N = len(s)
            dp = [0] * (N + 1)
            dp[N] = 1
            dp[N - 1] = 9 if s[N - 1] == '*' else 0 if s[N - 1] == '0' else 1
            for i in range(N - 2, -1, -1):
                if s[i] == '0':
                    continue
                if s[i] == '*':
                    dp[i] += 9 * dp[i + 1]
                    if s[i + 1] == '*':
                        dp[i] += 15 * dp[i + 2]
                    elif int(s[i + 1]) <= 6:
                        dp[i] += 2 * dp[i + 2]
                    else:
                        dp[i] += dp[i + 2]
                else:
                    dp[i] += dp[i + 1]
                    if s[i + 1] == '*':
                        if s[i] == '1':
                            dp[i] += 9 * dp[i + 2]
                        elif s[i] == '2':
                            dp[i] += 6 * dp[i + 2]
                    else:
                        if int(s[i:i + 2]) <= 26:
                            dp[i] += dp[i + 2]
                dp[i] %= 1000000007
            return dp[0]
    

  • 1
    R

    why do you need to take modulus of 1000000007 ?


  • 0

    @rcholic It is required by the problem.


  • 0
    C

    Brilliant idea! But why for s.charAt(i-1) == '*' && s.charAt(i-2) == '*' the transition function is dp[i] = (dp[i] + 15 * dp[i-2]) % mod rather than dp[i] = (dp[i] + 16 * dp[i-2]) % mod ? I think I can not figure out why we should consider s.charAt(i-1) == '0' as a new situation (my wrong solution only discussed s.charAt(i-1) == '*' and s.charAt(i-1) != '*'). Thx!


  • 0

    @Chen_Xiang
    Because ''*" represents 1 to 9 as it is said in the question. I used to make the same mistake.
    And also u need think about the substrings like "0*", it is not a valid substring to represent any alphabet.


  • 0
    C

    @Nakanu Thx!


  • 0

    @Chen_Xiang Ah, I just noticed the asterisk was used for the html format... Now it is correct...


Log in to reply
 

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