笔试回忆录-字符解码的情况数

题目 leetcode-91

一条包含字母 A-Z 的消息通过以下方式进行了编码:

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。
示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

说明

学习了Helper array的代码,非常佩服。

巧妙地利用字符串转整数的库函数,大大减少了代码量,而且使得程序看起来简介优雅。 在笔试中,我只想着用递归暴力解法,尽量拿一些分(然而真实情况是递归出bug,一分没有,悲惨)。

实际上,这题应该用动态规划。从第二三个字符开始,每个字符都是基于前两个字符来计算当前字符的值,这样可以很巧妙规避00的情况,比如1000,只要连续出现了两次0,或者是0作为开头的情况,都会导致后续的dp记录的结果都是0,非常巧妙。

相比较暴力递归,动态规划解答这题可以说非常优雅了,学艺不精,认了。

代码

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
		//dp数组记录
        int[] dp = new int[len];
		//判断首个字符情况
        dp[0]=s.charAt(0)=='0'?0:1;
		//从第二个字符开始遍历
        for(int i=1;i<len;i++){   
		//累加机制,例子:11。这里就会把i字符看出独立的个体,所以应该等于dp[i-1]的情况
            if(s.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
			//如果符合条件,就累加[i-2],只要2个字符拼接的值是小于26就可以
            if(s.charAt(i -1) != '0' && Integer.valueOf(s.substring(i-1,i+1)) <= 26){
			//注意如果是第二个字符要特殊考虑,避免数组边界溢出
                dp[i] += i > 1 ? dp[i - 2] : 1;
            }
        }
		//返回结果
        return dp[len-1];
    }
    
}