Description

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 10^9 + 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, 10^5].
  2. The input string will only contain the character ‘*’ and digits ‘0’ - ‘9’.

Solutions

  给定一串数字,其中含有星号,星号可以表示 0 到 9 任何一个数字,统计该串数字找出最多的字母组合。

1. DP-迭代

class Solution:
    def numDecodings(self, s: str) -> int:
        MOD = 10**9 + 7
        e0, e1, e2 = 1, 0, 0
        for c in 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, e1, e2 = f0 % MOD, f1, f2
        return e0
# 195/195 cases passed (368 ms)
# Your runtime beats 83.68 % of python3 submissions
# Your memory usage beats 50 % of python3 submissions (13.7 MB)

2. DP-递归

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s.startswith('0'):
            return 0
        n = len(s)
        dp = [0]*n
        dp[0] = self.ways(s[0])
        if n<2:
            return dp[0]
        dp[1] = self.ways(s[0], s[1]) + self.ways(s[1])*dp[0]
        
        for i in range(2, len(s)):
            dp[i] = (self.ways(s[i])*dp[i-1] + self.ways(s[i-1], s[i]) * dp[i-2])%(1000000007)
        return dp[-1]

    def ways(self, first, second = None):
        if first == '0' : return 0
        if not second:
            return 9 if first=='*' else 1
        if first>'2': return 0
        if first=='*':
            return 15 if second=='*' else 2 if second<='6' else 1
        elif first == '1': 
            return 9 if second=='*' else 1
        elif first =='2':
            return 6 if second=='*' else 0 if second>'6' else 1
# 195/195 cases passed (676 ms)
# Your runtime beats 51.84 % of python3 submissions
# Your memory usage beats 50 % of python3 submissions (17.5 MB)

3. 神奇解法

one = {'1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 1, '7': 1, '8': 1, '9': 1, '*': 9}
two = {'10': 1, '11': 1, '12': 1, '13': 1, '14': 1, '15': 1, '16': 1, '17': 1, '18': 1, '19': 1, '20': 1, '21': 1,
       '22': 1, '23': 1, '24': 1, '25': 1, '26': 1, '*0': 2, '*1': 2, '*2': 2, '*3': 2, '*4': 2, '*5': 2, '*6': 2,
       '*7': 1, '*8': 1, '*9': 1, '1*': 9, '2*': 6, '**': 15}

def numDecodings(self, s):
    """
    :type s: str
    :rtype: int
    """        
    dp = 1, one.get(s[:1], 0)
    
    for i in xrange(1, len(s)):
        dp = dp[1], (one.get(s[i], 0) * dp[1] + two.get(s[i-1: i+1], 0) * dp[0]) % 1000000007
    
    return dp[-1]

References

  1. 639. Decode Ways II