题目
- 给定一个信息包含字符串从A-Z,由下列的编码映射：
'A' -> 1
'B' -> 2
...
'Z' -> 26
- 给定一个字符串只包含数字，考虑有多少种方法去解码这个字符串
- 比如输入"12"输出2,输入"226"输出3
解题思路
- 这道题类似于爬梯子那道题的动态规划，需要考虑动态规划三要素，最优子结构，状态转移方程和边界条件
- 首先考虑最优子结构，我们考虑长度为n的字符串求它的解码方法设为F(n),如果此时第n个字符能够单独解码，那么它的解码方法F(n)=F(n-1),此时在考虑如果第n-1个字符和第n个字符能够组合成解码数字，那么F(n)=F(n-2)，此时就需要将这两种情况结合，同时还需要考虑第n个字符是否为0，如果为0那么只能和前一个字符结合考虑。总结起来就是如果10<=s[n-1]s[n]<=26&&s[n]!=0,此时F(n)= F(n-1)+F(n-2),如果10<=s[n-1]s[n]<=26&&s[n]==0，F(n) = 0 + F(n-2),其他情况就应该是F(n) = F(n-1);
- 根据此最优子结构可以勉强将状态方程看为F(n) = F(n-1) + F(n-2),需要加上以上种种附加条件
- 边界条件，当F(1) = 1, F(2) = 1, 其中F(1)不表示字符串中任何一个下标就是一个起始值1，F(2)表示的是字符串中第一个下标字符可解码方法为1，然后由此合并得到后续结果
- 解题方法：采用自顶向上合并的方法实现。首先我们确定第n个字符是否为0，如果为0那么此时F(n)=0,否则F(n)= F(n-1),然后再判断s[n-1]s[n]能否组合成1-26数字，如果可以此时F(n) += F(n-2),即是可以完成上述中的F(n) = F(n-1) + F(n-2)或者F(n) = F(n-2)步骤
- 以上解法可采用一个长度为s.length()+1的dp数组记录实现，但这样空间复杂度为O(n),本身我们只需要考虑两个数字F(n-1)和F(n-2)即可，可以声明两个变量pre表示F(n-1)，preSec表示F(n-2)，当我们监测s[n]时如果为0，我们需要将F(n)置为0，但此时的F(n)为下一个字符的pre，所以我们可以将pre直接置为0，因为如果s[n]不为0,F(n)=F(n-1)=pre,然后我们再监测s[n-1]s[n]组合符合要求，符合就将pre+preSecond赋值给pre，然后将当前的pre值给preSecond,否则直接将pre值给preSecond
源代码
class Solution {
public int numDecodings(String s) {
if (s.length() == 0 || s.charAt(0) == '0') return 0;
int pre = 1, preSec = 1;//表示前一个数和前两个数
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '0') pre = 0;
int temp = Integer.parseInt(s.substring(i-1, i+1));
if (temp >= 10 && temp <= 26) {
pre += preSec;
preSec = pre - preSec;
} else preSec = pre;
}
return pre;
}
}
