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;
}