91. Decode Ways解题报告

Description:

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

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

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

Example:

Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Link:

https://leetcode.com/problems/decode-ways/description/

解题方法：

1: DFS不能AC
每次取两个字符，比如s[i - 1]和s[i]这两个字符，判断这两个字符能组成一种还是两种情况然后再对s.substr(i)和s.substr(i + 1)进行判断。
2: DP
假设dp[i]为以i为结尾的字符串解码方式数量的总和。
假设当前index为i，当s[i]有效的时候，则dp[i] += dp[i - 1]。当s[i - 1]s[i]组成的字符串有效时，dp[i] += dp[i - 2]。
实际上我们并不需要一个额外的数组来储存，只需要两个变量来储存dp[i - 1]和dp[i - 2]即可。

Tips:

Time Complexity：

1、O(2^n)，DFS更适合求全部解码的结果，而不是计算有多少种解码的方法。
2、O(n)

完整代码：

//1、
int numDecodings(string s) {
        return helper(s, 0);
    }
    int helper(string& s, int start) {
        int len = s.size() - start;
        if(len <= 0 || s[start] == '0')
            return 0;
        if(len == 1)
            return 1;
        int val = atoi(s.substr(start, 2).c_str());
        if(len == 2) {
            if(val > 26 && s[start + 1] == '0')
                return 0;
            else if(s[start + 1] == '0' || val > 26)
                return 1;
            else
                return 2;
        }
        if(val > 26 && s[start + 1] == '0')
            return 0;
        if(s[start + 1] == '0')
            return helper(s, start + 2);
        if(val > 26)
            return helper(s, start + 1);
        return helper(s, start + 1) + helper(s, start + 2);
    }
//2、
int numDecodings(string s) {
    int len = s.size();
    if(!len || s[0] == '0')
        return 0;
    if(len == 1)
        return 1;
    int dp1 = 1, dp2 = 1;
    for(int i = 1; i < len; i++) {
        int curr = 0;
        if(isValid(s[i]))
            curr += dp2;
        if(isValid(s[i - 1], s[i]))
            curr += dp1;
        if(!curr)
            return 0;
        dp1 = dp2;
        dp2 = curr;
    }
    return dp2;
}
bool isValid(char c) {
    return c != '0';
}
bool isValid(char c1, char c2) {
    if(c1 == '0')
        return false;
    string s;
    s += c1;
    s += c2;
    int val = atoi(s.c_str());
    if(val > 26)
        return false;
    return true;
}