[LeetCode 91] 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.

Diffculty Medium

Similar Problems [LeetCode 70] Climbing Stairs Easy [LeetCode 96] Unique Binary Search Trees Medium

Analysis

类似爬楼梯问题，但要加很多限制条件。 算法问题通常很考验人的抽象能力，把一个抽象的问题可以归纳到一个算法实践上，作为 dp 问题最常见的思路，用 dp[i] 表示到位置 i 为止，可以表示的解码方式。 dp[N + 1]。

这里分几种情况：

• 如果字符串的第 i - 1 位和第 i 位不能组成有效二位数字，而且第 i 位不是 0 的话，说明我们是在第 i - 1 位的解码方法上继续解码。 dp[i] = dp[i s- 1]
• 如果字符串的第 i - 1 位和第 i 位能组成一个 10 到 26 的数字，说明我们是在第 i - 2 位的解码方法上继续解码。那么 dp[i] = dp[i - 1] + dp[i - 2]

所以，如果两个条件都符合，则 dp[i] = dp[i - 1] + dp[i - 2]，否则 dp[i] = dp[i - 1]。

Solutions

class Solution {
public:
    int numDecodings(string s) {
        if(s.length() == 0) return s.length();
        vector<int> dp(s.length() + 1);
        // 初始化第一种解码方式
        dp[0] = 1;
        // 如果第一位是0，则无法解码
        dp[1] = s[0] == '0' ? 0 : 1;
        for(int i = 2; i <= s.length(); i++){
            // 如果字符串的第i-1位和第i位能组成一个10到26的数字，说明我们可以在第i-2位的解码方法上继续解码
            if(s.substr(i-2, i)) >= string("10") && s.substr(i-2, i) <= string("26")){
                dp[i] += dp[i - 2];
            }
            // 如果字符串的第i-1位和第i位不能组成有效二位数字，在第i-1位的解码方法上继续解码
            if(s.substr(i-1, i) != string("0")){
                dp[i] += dp[i - 1];
            }
        }
        return dp[s.length()];
    }
}