## 题目描述：

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 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'.

## 解题思路：

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

## 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
``````

Pingbacks已关闭。