Easy Java DP Solution with detailed explanation


  • 0
    G

    Inspired by decode ways I
    Single character --> single letter --> easy handle
    Double character --> single letter --> 4 cases

    1. num + num
    2. "*"+ num
    3. num + "*"
    4. "" + ""
    public int numDecodings(String s) {
        if(s.length() == 0 || s == null || s.charAt(0) == '0')  return 0;
        long[] dp = new long[s.length() + 1];
        // initialize dp[0] and dp[1]
        dp[0] = 1;
        if(s.charAt(0) == '*') {
            dp[1] = 9;
        } else {
            dp[1] = 1;
        }
        for(int i = 2; i <= s.length(); i++) {
            
            // first part: single character --> single letter, e.g 1->A, 2->B, * -> (1-9)
            if(s.charAt(i - 1) == '*')  dp[i] = 9 * dp[i - 1];
            else if(s.charAt(i - 1) != '0')  dp[i] = dp[i - 1];
            
            
            // Second part: two characters --> single letter -- 4 cases
            if(s.charAt(i - 1) != '*') { 
                if(s.charAt(i - 2) != '*') { 
                    // case 1: num + num
                    int num = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                    if(num >= 10 && num < 27)  dp[i] += dp[i - 2];
                } else {
                    // case 2: * + num
                    // current >= 7 means, * can just be 1.   e.g: 17 is valid, 27 is not valid
                    if(s.charAt(i - 1) - '0' >= 7)  dp[i] += dp[i - 2]; 
                    else dp[i] += 2 * dp[i - 2];  // current is less than 7, * can be 1 and 2.  e.g: 14 and 24 are valid
                }
            }
            
            else if(s.charAt(i - 1) == '*') {  
                //case 3: num + *
                if(s.charAt(i - 2) - '0' == 1)  dp[i] += 9 * dp[i - 2];  // 11 -> 19
                if(s.charAt(i - 2) - '0' == 2)  dp[i] += 6 * dp[i - 2];  // 21 -> 26
                
                //case 4: * + *
                if(s.charAt(i - 2) == '*') {
                    dp[i] += 15 * dp[i - 2];  // 11 -> 19 + 21 -> 26
                }
            }
            
            dp[i] = dp[i] % 1000000007;
        }
        return (int)dp[s.length()];
    }

Log in to reply
 

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