Java DP


  • 0
    W

    The difference of this problem compared with Decode Ways is that coefficient is no longer 1, we need to consider '*'. When calculate the possible combination of s[i-1, i], I consider following 4 situations:

    1. s[i-1] = number, s[i] = number
    2. s[i-1] = number, s[i] = *
    3. s[i-1] = *, s[i] = number
    4. s[i-1] = *, s[i] = *

    DP function is:

    dp[i+1] = one*dp[i] + two*dp[i-1]
    
            int n = s.length();
            if(n == 0) return 0;
            if(s.charAt(0) == '0') return 0;
    
            long[] dp = new long[n + 1];
            dp[0] = 1;
            dp[1] = s.charAt(0) == '*' ? 9 : 1;
            int mod = 1000000007;
    
            for(int i = 1; i < n; i++) {
                int one = s.charAt(i) == '*' ? 9 : (s.charAt(i) == '0' ? 0 : 1);
                dp[i+1] = (dp[i] % mod * one) % mod;
                
                char last = s.charAt(i-1);
                if((last != '*' && last > '2') || last == '0') continue;
                char cur = s.charAt(i);
                int two = 0;
                if(cur != '*' && last != '*') {
                    if(last == '2' && cur > '6') two = 0;
                    else two = 1;
                }
                else if(cur != '*') {
                    if(cur > '6') two = 1; else two = 2;
                }
                else if(last != '*') {
                    if(last == '1') two = 9;
                    else two = 6;
                }
                else two = 15;
                dp[i+1] = (dp[i+1] + dp[i-1] % mod * two) % mod;
                
            }
            return (int) dp[n];
    

Log in to reply
 

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