[C++]LeetCode: 55 Decode Ways

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.

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.

思路：

设置动态数组dp[i], dp[i]表示字符串 s[0,1,2,....,i-1]的decode way的个数。

注意，如果序列中有不能匹配的0，那么解码的方法是0，比如序列012，,100（第二个0可以和1组成10，但是第三个0不能匹配）。

分成两种情况讨论，考虑末尾一个数字以及考虑末尾两个数字。动态规划方程：

初始条件：dp[0] = 1(根据判断两个数字dp[2] += dp[0] 确定), dp[1] = (s[0] == '0') ? 0 :1

递推公式：1.考虑s[0,1,2,...,i-1]末尾一个数字当做一个字母考虑，dp[i]【1】 = s[i-1] == 0 ? 0 : dp[i-1]

2.考虑s[0,1,2,...,i-1]末尾两个数字当做一个字母考虑，dp[i]【2】 = isValid(s[i-2, i-1]) == true ? dp[i-2] ：0

3. dp[i] = dp[i]【1】+ dp[i]【2】

Attention:

1. 初始条件dp[0]的设置，需要根据代码具体含义确定，需符合实际意义（dp[2] += dp[0]，此处dp[0]表示s[0,1]代表一个字母，所以取1） 。

2. 如果序列中有不能匹配的0，那么解码的方法是0。 这点容易忽视，一定要注意。如果某字符为0，则不能解码，只考虑它是否可以前一个字符组成合法字符。

3. 加入合法字符判断的helper程序（isValid()），可以使代码含义更加清晰。但是也可以采取直接判断。代码如下：

for(int i = 2; i <= len; i++)
        {
            if(s[i-1] != '0')
                dp[i] = dp[i-1];
            else dp[i] = 0;
            if(s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6'))
                dp[i] += dp[i-2];
        }

4. 动态方程的递推方式，以及dp[i]的含义确定，需要准确和考虑全面。

复杂度：O(N)

AC Code:

class Solution {
public:
    int numDecodings(string s) {
        int len = s.length();
        if(len == 0) return 0;
        
        //dp[i]表示s[0,1,...,i-1]的解码方法数目
        int dp[len+1];
        
        //初始化dp[0],dp[1]
        dp[0] = 1;
        if(s[0] != '0')
        {
            dp[1] = 1;
        }
        else
        {
            dp[1] = 0;
        }
        
        for(int i = 2; i <= len; i++)
        {
            //如果末尾数字为无效0，则dp为0
            if(isValid(s.substr(i-1, 1)))
            {
                dp[i] = dp[i-1];
            }
            else
            {
                dp[i] = 0;
            }
            
            if(isValid(s.substr(i-2, 2)))
            {
                dp[i] += dp[i-2];
            }
        }
        
        return dp[len];
    }

public:
    bool isValid(string str)
    {
        //如果str中含无效的0,如“02”，解码失败
        if(str[0] == '0')
            return false;
        int num = std::stoi(str);
        if(num >= 1 && num <= 26)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};