欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[LeetCode] 639. Decode Ways II 解码方法 II

程序员文章站 2022-07-05 14:48:15
...

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character '*', return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I". 

Example 2:

Input: "1*"
Output: 9 + 9 = 18

Note:

  1. The length of the input string will fit in range [1, 105].
  2. The input string will only contain the character '*' and digits '0' - '9'.

91. Decode Ways  的拓展,这次字符串里面可能含有'*', 它可以1~9中的任何一个,求总的解码方法数。

解法:还是DP,主要是如何处理'*'。

Java:

    public int numDecodings(String s) {
        /* initial conditions */
        long[] dp = new long[s.length()+1];
        dp[0] = 1;
        if(s.charAt(0) == '0'){
            return 0;
        }
        dp[1] = (s.charAt(0) == '*') ? 9 : 1;

        /* bottom up method */
        for(int i = 2; i <= s.length(); i++){
            char first = s.charAt(i-2);
            char second = s.charAt(i-1);

            // For dp[i-1]
            if(second == '*'){
                dp[i] += 9*dp[i-1];
            }else if(second > '0'){
                dp[i] += dp[i-1];
            }
            
            // For dp[i-2]
            if(first == '*'){
                if(second == '*'){
                    dp[i] += 15*dp[i-2];
                }else if(second <= '6'){
                    dp[i] += 2*dp[i-2];
                }else{
                    dp[i] += dp[i-2];
                }
            }else if(first == '1' || first == '2'){
                if(second == '*'){
                    if(first == '1'){
                       dp[i] += 9*dp[i-2]; 
                    }else{ // first == '2'
                       dp[i] += 6*dp[i-2]; 
                    }
                }else if( ((first-'0')*10 + (second-'0')) <= 26 ){
                    dp[i] += dp[i-2];    
                }
            }

            dp[i] %= 1000000007;
        }
        /* Return */
        return (int)dp[s.length()];
    } 

Python:

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0 or s[0] == '0':
            return 0
        
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 9 if s[0] == '*' else 1
        
        for i in xrange(2, len(dp)):
            first = s[i-2]
            second = s[i-1]
            # for dp[i-1]
            if second == '*':
                dp[i] = dp[i-1] * 9
            elif second != '0':
                dp[i] = dp[i-1]
            
            # for dp[i-2]
            if first == '*':
                if second == '*':
                    dp[i] += 15 * dp[i-2]
                elif second <= '6':
                    dp[i] += 2 * dp[i-2]
                else:
                    dp[i] += dp[i-2]
            elif first == '1' or first == '2':
                if second == '*':
                    if first == '1':
                        dp[i] += 9 * dp[i-2]
                    else:
                        dp[i] += 6 * dp[i-2]
                elif first == '1' or (first == '2' and second <= '6'):
                    dp[i] += dp[i-2]   
                    
            dp[i] %= 1000000007         
                    
        return dp[-1]     

Python:

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

C++:

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size(), M = 1e9 + 7;
        vector<long> dp(n + 1, 0);
        dp[0] = 1;
        if (s[0] == '0') return 0;
        dp[1] = (s[0] == '*') ? 9 : 1;
        for (int i = 2; i <= n; ++i) {
            if (s[i - 1] == '0') {
                if (s[i - 2] == '1' || s[i - 2] == '2') {
                    dp[i] += dp[i - 2];
                } else if (s[i - 2] == '*') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    return 0;
                }
            } else if (s[i - 1] >= '1' && s[i - 1] <= '9') {
                dp[i] += dp[i - 1];
                if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) {
                    dp[i] += dp[i - 2];
                } else if (s[i - 2] == '*') {
                    dp[i] += (s[i - 1] <= '6') ? (2 * dp[i - 2]) : dp[i - 2];
                }
            } else { // s[i - 1] == '*'
                dp[i] += 9 * dp[i - 1];
                if (s[i - 2] == '1') dp[i] += 9 * dp[i - 2];
                else if (s[i - 2] == '2') dp[i] += 6 * dp[i - 2];
                else if (s[i - 2] == '*') dp[i] += 15 * dp[i - 2];
            }
            dp[i] %= M;
        }
        return dp[n];
    }
};  

C++:

class Solution {
public:
    int numDecodings(string s) {
        long e0 = 1, e1 = 0, e2 = 0, f0, f1, f2, M = 1e9 + 7;
        for (char c : s) {
            if (c == '*') {
                f0 = 9 * e0 + 9 * e1 + 6 * e2;
                f1 = e0;
                f2 = e0;
            } else {
                f0 = (c > '0') * e0 + e1 + (c <= '6') * e2;
                f1 = (c == '1') * e0;
                f2 = (c == '2') * e0;
            }
            e0 = f0 % M;
            e1 = f1;
            e2 = f2;
        }
        return e0;
    }
};

  

 

类似题目:

[LeetCode] 91. Decode Ways 解码方法

 

All LeetCode Questions List 题目汇总