题目描述：

LeetCode 639. Decode Ways II

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⁹ + 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⁵].
2. The input string will only contain the character '*' and digits '0' - '9'.

题目大意：

信息包含字符A-Z以及通配符*，A-Z编码为1-26，*表示编码后的数字可能为1-9

给定编码后的信息，求原始信息的可能个数。答案可能会很大，对10^9 + 7取模

解题思路：

动态规划（Dynamic Programming）

令dp[x]表示 s[0 .. x] 对应的原串的可能个数

状态转移方程如下：

dp[x] = (dp[x - 2] * dmap[s[x - 1 .. x]] + dp[x - 1] * dmap[s[x]]) % MOD

上式中，dmap[s]表示子串s对应的原串的可能个数，分别令s = '0', '1', ..., '9', '*'，以及'00', '01', ... '*9', '**'对dmap进行初始化

Python代码

class Solution(object):
    def __init__(self):
        dmap = collections.defaultdict(int)
        ch = '0123456789*'
        for m in ch:
            if m == '*': dmap[m] = 9
            elif '1' <= m <= '9': dmap[m] = 1
            for n in ch:
                s = m + n
                if m == '*':
                    if n == '*': dmap[s] = 15
                    elif '0' <= n <= '6': dmap[s] = 2
                    else: dmap[s] = 1
                elif m == '1':
                    if n == '*': dmap[s] = 9
                    else: dmap[s] = 1
                elif m == '2':
                    if n == '*': dmap[s] = 6
                    elif '0' <=  n <= '6': dmap[s] = 1
        self.dmap = dmap
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        MOD = 10**9 + 7
        ans = 0
        dp1 = dp2 = 1
        lc = '-'
        for x, c in enumerate(s):
            ans = (dp1 * self.dmap[c] + dp2 * self.dmap[lc + c]) % MOD
            lc = c
            dp1, dp2 = ans, dp1
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/07/09/leetcode-decode-ways-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码