LeetCode 92 Decode Ways

原文

A message containing letters from A-Z is being encoded to numbers the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

翻译

一条信息包括字母A-Z，它们按如下方式被映射到相应的数字：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个包含数字的编码信息，得出一共有多少种可能的编码方式。

例如，
给定的编码信息是“12”，它可能是“AB”（1 2），也可能是“L”（12）。

所以“12”的编码方式有2种。

代码

题目看了半天才看懂，沮丧脸……

由于是在LeetCode上尝试分类结题，这题被归在了String下面，我以为只是简单的字符串操作就可以搞定，后来发现遍历过程是动态的，也就是要用到DP了。

由于现在对DP还不是很熟练，所以没能解出来，先借用大神的代码来占个坑吧。

bool valid(string s) {
    if (s[0] == '0')
        return false;
    if (s[0] > '2' || (s[0] == '2' && s[1] > '6'))
        return false;
    return true;
}

int numDecodings(string s) {
    int len = s.length();
    if (len == 0 || s[0] == '0') return 0;
    vector<int> dp(len + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i - 1] != '0') 
            dp[i] += dp[i - 1];
        if (valid(s.substr(i - 2, 2))) 
            dp[i] += dp[i - 2];
        if (dp[i] == 0) 
            return 0;
    }
    return dp[len];
}