LeetCode—91. Decode Ways
LeetCode—91. Decode Ways
题目
https://leetcode.com/problems/decode-ways/description/
找出字符串的解码方式数。
思路及解法
动态规划的题目。
我们用dp[i]表示到前i个字符,总计的解码方式。
考虑递归关系。s[i]的值是我们需要关心的问题,如果它是0,此时s[i]必须和s[i-1]组合,所以需要去看s[i-1]的值,s[i-1]若是1或者2,没有增加解码方式,也就是dp[i]=dp[i-1],若是s[i-1]大于2,那么应该return 0,因为两个字符的组合非法,所以整体不能被解码。
如果s[i]不为0,还需要细分情况讨论。若是s[i-1]为1,或者s[i-1]为2且s[i]在1到6之间(包括了11-19和21-26的情况),那么s[i]既可以单独形成一个解码(解码方式有dp[i-1]),也可以和s[i-1]组合形成一个解码(解码方式有dp[i-2]),所以总体就是dp[i]=dp[i-1]+dp[i-2]。当时我看到两者直接相加的时候想了一会,难道dp[i-1]和dp[i-2]两者没有重复的情况吗?毕竟dp[i-1]是由dp[i-2]得到的。其实是这样的,因为我们把s[i]加进来了,他若是和s[i-1]组合形成一种解码方式,这种解码方式中包含着他和s[i-1]组合成的一个元素,他若是不和s[i-1]组合,单独自己形成一种解码方式,这时候是不包含上一种情况的我们提到的元素的,所以这两种解码方式是互斥的,所以加和没有问题。
对于s[i]不为0的其他情况,s[i]只能和s[i-1]组合形成解码,所以 dp[i] = dp[i-1]。
另外再就是初始化的问题了,我们要初始化dp[0]和dp[1],分情况讨论比较简单,直接看代码就好了。
代码
class Solution {
public int numDecodings(String s) {
if(s.length() == 0) return 0;
char[] digits = s.toCharArray();
int[] dp = new int[digits.length];
dp[0] = digits[0]=='0'? 0 : 1;
if(dp[0]==0 || digits.length==1) return dp[0];
if(digits[0]=='1'&&'1'<=digits[1]&&digits[1]<='9' || digits[0]=='2'&&'1'<=digits[1]&&digits[1]<='6'){
dp[1] = 2;
}else if(digits[1]=='0'&&digits[0]>'2'){
return 0;
}else{
dp[1] = 1;
}
for(int i=2; i<digits.length; i++){
if(digits[i]!='0'){
if(digits[i-1]=='1' || digits[i-1]=='2'&&'1'<=digits[i]&&digits[i]<='6'){
dp[i]=dp[i-1]+dp[i-2];
}else{
dp[i] = dp[i-1];
}
}else{
if(digits[i-1]=='1'||digits[i-1]=='2'){
dp[i] = dp[i-2];
}else{
return 0;
}
}
}
return dp[digits.length-1];
}
}