mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
67 lines
2.3 KiB
Markdown
67 lines
2.3 KiB
Markdown
# [91. Decode Ways](https://leetcode.com/problems/decode-ways/)
|
||
# 思路
|
||
## 思路一
|
||
我们可以这样看待这个题。将`s`看成是一个充满障碍的路，每个数字代表一个障碍，我们需要从左到右通过这条路，需要满足的条件是:
|
||
* 一次只能越过一个或者两个障碍;
|
||
* 一次性越过的（一个或两个）障碍所代表的数属于[1,26]。
|
||
```
|
||
Path s: _ 2 _ 2 _ 6 _
|
||
Index: 0 1 2 3
|
||
```
|
||
对于上例，可能的路径就是`0->1->2->3`、`0->2->3`、`0->1->3`。
|
||
|
||
所以我么可以通过动态规划解此题，开辟一个大小为`s.size()+1`的数组`dp`, `dp[i]`代表从最左边(index=0)到达index=i的所有情况数，最终所求即dp的最后一个元素。所以`dp[0]`初始为1, 有两种方式可到达i:
|
||
1. 从i-1越过障碍`s[i-1]`到达i；
|
||
2. 从i-2越过障碍`s[i-2]`和`s[i-1]`到达i；
|
||
|
||
情况1需要满足的条件是`s[i - 1] != 0`，情况2需要满足的条件是`s[i-2]`和`s[i-1]`组成的数字属于[1,26]。
|
||
|
||
时空复杂度均为O(n)
|
||
|
||
## 思路二
|
||
仔细分析思路一发现，我们每次循环只需要用到`dp[i]`、`dp[i - 1]`和`dp[i - 2]`，所以我们没必要开辟一个dp数组，而用`cur`、`pre`和`pre_pre`分别代表`dp[i]`、`dp[i - 1]`和`dp[i - 2]`就可以了。
|
||
|
||
时间复杂度O(n)，空间复杂度O(1)
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int numDecodings(string s) {
|
||
if(s[0] == '0') return 0;
|
||
vector<int>dp(s.size() + 1, 0);
|
||
dp[0] = 1;
|
||
for(int i = 1; i < dp.size(); i++){
|
||
dp[i] = (s[i - 1] == '0') ? 0: dp[i - 1]; // 方式1
|
||
if(i > 1){ // 方式2
|
||
if(s[i - 2] == '1') dp[i] += dp[i - 2];
|
||
else if(s[i - 2] == '2' && s[i - 1] < '7') dp[i] += dp[i - 2];
|
||
}
|
||
}
|
||
return dp.back();
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int numDecodings(string s) {
|
||
if(s[0] == '0') return 0;
|
||
int cur, pre = 1, pre_pre;
|
||
for(int i = 1; i < s.size() + 1; i++){
|
||
cur = (s[i - 1] == '0') ? 0: pre;
|
||
if(i > 1){
|
||
if(s[i - 2] == '1') cur += pre_pre;
|
||
else if(s[i - 2] == '2' && s[i - 1] < '7') cur += pre_pre;
|
||
}
|
||
pre_pre = pre;
|
||
pre = cur;
|
||
}
|
||
return cur;
|
||
}
|
||
};
|
||
```
|