原题地址：https://leetcode.cn/problems/decode-ways/
题解
由于编码最多只到26，因此组合解析的情况最多也只有两个字符
开一个二维数组int[2][s.length()]，其中：
- dp[0][i]表示第i个字符独立解析的情况下的可能性
- dp[1][i]表示第i个字符和第i-1个字符组合解析的情况下的可能性
对于一般情况，我们可以推出：
- 第i个字符在独立解析的情况下，与第i-1个字符的解析状态无关，可能性为第i-1个字符的两种解析状态可能性之和
- 有dp[0][i]=dp[0][i-1]+dp[1][i-1]
- 第i个字符在组合解析且组合情况符合要求[10,26]的情况下，则继承第i-1个字符独立解析的状态的可能性
- 第i个字符在组合解析的情况下，若组合情况不符合[10,26]，则表示不能与第i个字符组合解析
考虑几个特殊情况：
- 当第i个字符为0时，只能采用组合解析的情况，0无法被独立解析
- 有dp[0][i]=0;
- 当组合解析的情况即dp[1][i]也为0时，由于第i个字符的可能性仅与第i-1个字符有关，因此最终输出结果必然是0，可以直接返回0
- 当为第一个字符时，自然无法与前一个字符组合解析，所以有
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
| class Solution {
public int numDecodings(String s) {
int[][] dp=new int[2][s.length()];
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='0'){
if(i==0)return 0;
dp[0][i]=0;
if((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')>=10&&(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')<=26)
dp[1][i]=dp[0][i-1];
else
return 0;
}else if(i==0){
dp[0][i]=1;
dp[1][i]=0;
}else{
dp[0][i]=dp[0][i-1]+dp[1][i-1];
if((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')>=10&&(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')<=26)
dp[1][i]=dp[0][i-1];
else
dp[1][i]=0;
}
}
return dp[1][dp[1].length-1]+dp[0][dp[0].length-1];
}
}
|
观察代码发现，当遍历到i时，dp[x][i]的状态仅与dp[x][i-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
| class Solution {
public int numDecodings(String s) {
int combined=0,uncombined=1,tmp;
if(s.charAt(0)=='0')return 0;
for(int i=1;i<s.length();i++){
if(s.charAt(i)=='0'){
if(i==0)return 0;
if((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')>=10&&(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')<=26)
combined=uncombined;
else
return 0;
uncombined=0;
}else{
tmp=combined+uncombined;
if((s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')>=10&&(s.charAt(i-1)-'0')*10+(s.charAt(i)-'0')<=26)
combined=uncombined;
else
combined=0;
uncombined=tmp;
}
}
return combined+uncombined;
}
}
|
