Leetcode刷题详解——解码方法

1. 题目链接：91. 解码方法

2. 题目描述：

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
1
2
3
4

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
1
2
3

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
1
2
3

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
1
2
3

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

3. 算法思路：

1. 状态表示：

用i位置左结尾

2.状态转移方程：

关于i位置的编码情况，我们可以分为下面两种情况：

• 让i位置上的数单独解码成一个字母
• 让i位置上的数与i-1位置上的数结合，解码成一个字母

下面我们就上面的两种解码情况，继续分析：

1. 让i位置上的数单独解码成一个字母，就存在【解码成功】和【解码失败】两种情况 ：

   1. 解码成功：当i位置上的数在[1,9]之间的时候，说明i位置上的数是可以单独解码的，那么此时[0,i]区间上的解码方法应该等于[0,i-1]区间上的解码方法。因为[0,i-1]区间上的所有解码结果，后面填写一个i位置解码后的字母就可以了。此时dp[i]=dp[i-1]

   2. 解码失败：当i位置上的数是0的时候，说明i位置上的数是不能单独解码的，那么此时[0,i]区间上不存在解码方法。因为i位置如果单独参与解码，但是解码失败了，那么前面做的努力就白费了。此时dp[i]=0;

2. 让i位置上的数与i-1位置上的数结合在一起，解码成一个字母，也存在【解码成功】和【解码失败】两种情况：

   1. 解码成功：当结合的数在[10,26]之间的时候，说明[i-1,i]两个位置是可以解码成功的，那么此时[0,i]区间上的解码方法应该等于[0,i-2]区间上的解码方法，原因同上。此时dp[i]=d[i-2]

   2. 解码失败：当结合的数在[0,9]和[27,99]之间的时候，说明两个位置结合后解码失败（这里一定要注意00 01 02 03 04……这几种情况），那么此时[0,i]区间上的解码方法就不存在了，原因依旧同上，此时dp[i]=0

综上所述：dp[i]最终结果应该是上面四种情况下，解码成功的两种是累加和（因为我们关心的是解码方法，既然解码失败，就不用加入到最后结果中去），因此可以得到状态转移方程（dp[i]默认初始化为0）：

1. 当s[i]上的数在[1,9]区间时：dp[i]+=dp[i-1]

2. 当s[i-1]与s[i]上的数结合后，在[10,26]之间的时候：dp[i]+=dp[i-2];

如果上述两个判断不成立，说明没有解码方法，d[i]就是默认值0

3. 初始化：

方法1（直接初始化）：
由于可能要用到i-1以及i-2位置上的dp值，因此要先初始化前两个位置

初始化dp[0]:

1. 当s[0]==‘0’时，没有编码成功，结果dp[0]=0

2. 当s[0]!=‘0’时，能编码成功，dp[0]=1

初始化dp[1]:

1. 当s[1]在[1,9]之间时，能单独编码，此时dp[1]+=dp[0]（原因同上，dp[1]默认为0）
2. 当s[0]与s[1]结合后的数在[10,26]之间时，说明在前两个字符中，又有一种编码方式，此时dp[1]+=1

方法2（添加辅助位置初始化）：

可以在最前面加上一个辅助结点，帮助我们初始化，使用这种技巧要注意两个点：

辅助结点里面的值要保证后续填表正确

下标的映射关系

4. 填表顺序

从左往右

5. 返回值

应该返回dp[n-1]的值，表示在[0,n-1]区间上的编码方法

4. C++算法代码

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        //创建一个dp表
        vector dp(n);
        //初始化前两个位置
        dp[0]=s[0]!='0';//说明dp[0]在1~9之间
        if(n==1) return dp[0];//处理边界情况
        if(s[1]<='9'&&s[1]>='1') dp[1]+=dp[0];
        int t=(s[0]-'0')*10+s[1]-'0';
        if(t>=10&&t<=26) dp[1]+=1;
        
        //填表
        for(int i=2;i='1') dp[i]+=dp[i-1];
            //如果和前面的一个数联合起来编码
            int t=(s[i-1]-'0')*10+s[i]-'0';
            if(t>=10&&t<=26) dp[i]+=dp[i-2];
        }
        //返回结果
        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26