> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/string-match/decode-ways/decode-ways-ii.md).

# 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

## Thoughts

给定一个由数字和*组成的字符串，数字可以转化成对应的字母(e.g. 1->A, 2->B, ...,26->Z)，*可看作数字\[1, 9]，问一共有多少种潜在的转化方法。根据字符串长度分成了N步，每步action为把S\[i]或S\[i - 1: i]转化成字母，因此DP\[i]表前i个字符有多少种转化方式。字符串为空时看作有1种转化方式。\*号时由于有多种可能，相当于把前面的解做乘法，并分类讨论所有的可能性。

## Code

```
/*
 * @lc app=leetcode id=639 lang=cpp
 *
 * [639] Decode Ways II
 */

// @lc code=start
class Solution {
public:
    int numDecodings(string s) {
        const int N = s.length(), M = 1000000007;
        vector<long> dp(N + 1, 0);
        dp[0] = 1;
        if (s[0] == '*') dp[1] = 9;
        else if (s[0] != '0') dp[1] = 1;
        for (int i = 2; i <= N; ++i) {
            const auto c = s[i - 1];
            if (c == '*') {
                dp[i] = dp[i - 1] * 9;
                switch (s[i - 2]) {
                    case '1':
                        dp[i] += dp[i - 2] * 9;
                        break;
                    case '2':
                        dp[i] += dp[i - 2] * 6;
                        break;
                    case '*':
                        dp[i] += dp[i - 2] * 15;
                    default:
                        break;
                }
            } else {
                if (c != '0') dp[i] = dp[i - 1];
                switch (s[i - 2]) {
                    case '1':
                        dp[i] += dp[i - 2];
                        break;
                    case '2':
                        if (c <= '6') dp[i] += dp[i - 2];
                        break;
                    case '*':
                        if (c <= '6') dp[i] += dp[i - 2] * 2;
                        else dp[i] += dp[i - 2];
                    default:
                        break;
                }
            }
            dp[i] %= M;
        }
        return (int)dp[N]; 
    }
};
// @lc code=end


```

```
class Solution {
    public int numDecodings(String s) {
        int mod = 1000000007;
        long[] f = new long[s.length() + 1];
        f[0] = 1;
        if (s.charAt(0) == '0') {
            return 0;
        }
        f[1] = s.charAt(0) == '*' ? 9 : 1;

        for (int i = 2; i <= s.length(); i++) {
            char first = s.charAt(i - 2);
            char sec = s.charAt(i - 1);

            // f[i - 1]
            if (sec == '*') {
                f[i] += 9 * f[i - 1]; // 1 ~ 9
            } else if (sec > '0') {
                f[i] += f[i - 1];
            }

            if (first == '*') {
                if (sec == '*') {
                    f[i] += 15 * f[i - 2]; // 11 ~ 19, 21 ~ 26: 15
                } else if (sec <= '6') {
                    f[i] += 2 * f[i - 2]; // first = 1, 2
                } else {
                    f[i] += f[i - 2]; // first = 1;
                }
            } else if (first == '1') {
                if (sec == '*') {
                    f[i] += 9 * f[i - 2];
                } else {
                    f[i] += f[i - 2];
                }
            } else if (first == '2') {
                if (sec == '*') {
                    f[i] += 6 * f[i - 2];
                } else if (sec <= '6') {
                    f[i] += f[i - 2];
                }
            }
            f[i] %= mod;
        }

        return (int)f[s.length()];
    }
}
```

## Analysis

时间复杂度还是O(N), 空间可以O(1), 因为实际只用了i - 1和i - 2.