[C++]LeetCode: 55 Decode Ways

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