【4.21】LeetCode每日一题· 解码方法

2021年04月21日 15时14分

标签： LeetCode 动态规划

## 题目描述
一条包含字母`A-Z`的消息通过以下映射进行了**编码**：
```
'A' -> 1
'B' -> 2
...
'Z' -> 26
```

要**解码**已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"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）。
```

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

#### 示例3
```
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
```

#### 示例4
```
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
```

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

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/decode-ways%0A "题目链接")

## 解题思路
动态规划。如果设
```
dp[i] 表示 s[0..i]（不包含i）可以解码的总数
```

对于某一个串`s[0..i+1]`：
* 如果`s[i]`不为0，那么可以将`s[0..i]` 的分割后，再将`s[i]`单独分割出来，因此`s[0..i+1]`的分割方法包含`s[0..i]`的分割方法；
* 如果`s[i-1]s[i]`为`"10"~"26"`之间的数，那么可以将`s[0..i-1]` 的分割方法拼上`s[i-1]s[i]`这一分割，得到`s[0..i+1]`的分割方法，因此`s[0..i+1]`的分割方法包含`s[0..i-1]`的分割方法；
综上，可以得出状态转移方程：
```python
dp[i] = (dp[i-1] if s[i-1] != '0' else 0) + (dp[i-2] if s[i-2] != '0' and s[i-2]s[i-1] <= "26" else 0)
```

Tip: 思路中最重要的一步是，要想到通过`s[0..i-1]`和`s[0..i]`的分割方法导出`s[0..i+1]`的分割方法，和爬楼梯这一道题有异曲同工之妙。
一开始思考的是如果取`s[i..j]`中的某一点`k`，那么`s[i..k]`有一些分割方法，`s[k+1..j]`也有一些分割方法，将两部分的分割方法数相乘得到`s[i..j]`的分割方法数。这一状态转移是有问题的，因为不能保证子问题求解得到的答案中没有重复。例如对于`"221"`，`2|(2|1)`和`(2|2)|1`两者的分割实际上是一样的。
在蓝桥杯做题的时候也碰到过这种情况，此时就不应该在这一思路上死磕了，考虑去重之类的，而应换一种状态的定义方法。
## 代码
```cpp
class Solution {
public:
    //dp[i] := s[0..i]（不包含i）可以解码的总数
    //dp[i] = (dp[i-1] if s[i-1] != '0' else 0) + (dp[i-2] if s[i-2] != '0' and s[i-2]s[i-1] <= "26" else 0)
    //dp[0] = 1
    inline int string2num(string& s, int l, int r){
        int num = 0;
        for(int i = l; i <= r; i++){
            num *= 10;
            num += s[i] - '0';
        }
        return num;
    }
    int numDecodings(string s) {
        const int n = s.length();
        int dp[n+1];
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            dp[i] = 0;
            if(s[i-1] != '0'){
                dp[i] += dp[i-1];
            }
            if(i-2>=0 && s[i-2] != '0' && string2num(s, i-2, i-1) <= 26){
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
};
```

## 用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：5.8 MB，在所有 C++提交中击败了98.23%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.21】LeetCode每日一题· 解码方法

所有评论

暂无评论

新增评论