639. Decode Ways II

https://leetcode.com/problems/decode-ways-ii/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 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.