• 问题来源
• 问题简介

  

解题思路

• count(c): c字符的解码方法数，有效值是 1 - 9
• count(a, b): 数字ab的解码方法数，有效值为 10 - 26。
• dp[i]: 前i个字符串解码方法数
  • count(s[1]): i = 1
  • dp[1] * count(s[2]) + count(s[1], s[2]): i = 2
  • dp[i-1] * count(s[i]) + dp[i-2] * count(s[i-1], s[i]): 2 <= i <= n;
• 则结果为 dp[n]

Code

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        long dp[n], c_prev, n_c;
        dp[0] = noCombine(1, s[0]);
        if (n < 2) {
            return dp[0];
        }
        dp[1] = noCombine(dp[0], s[1]) + combine(1, s[0], s[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = (noCombine(dp[i-1], s[i]) + combine(dp[i-2], s[i-1], s[i])) % 1000000007;

        }
        return dp[n-1];
    }
    long noCombine(long dp, char s) {
        if (s == '0') {
            return 0;
        }
        return dp * (s == '*' ? 9 : 1);
    }
    long combine(long dp, char s1, char s2) {
        int count = 1;
        if (s1 == '1') {
            if (s2 == '*') {
                count = 9;
            }
        } else if (s1 == '2') {
            if (s2 == '*') {
                count = 6;
            } else if (s2 > '6') {
                count = 0;
            }
        } else if (s1 == '*') {
            if (s2 == '*') {
                count = 15;
            } else if (s2 <= '6') {
                count = 2;
            }
        } else {
            count = 0;
        }
        return count * dp;
    }
};

运行结果