46 把数字翻译成字符串

牛客

描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

牛客把原书的条件改了，原书时 'a'->0，现在必须把 '0' 当作无法编码

使用动态规划求解，如果当前字符不为 '0' 则当前字符的编码方法和到当前字符前一个字符的编码方法相同，否则为 0。如果当前字符可以和上一个字符一起编码，则当前字符的编码方法加上到当前字符上上个字符的编码方法数。

f(k) = (当前字符可以编码 ? f(k-1):0 ) + (当前字符可以和上一个字符编码 ? f(k-2):0 )

public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        if(nums==null || nums.length()==0 || "0".equals(nums)) return 0;
        if(nums.length()==1) return 1;
        int pre1 = 1;
        int pre2 = 0;
        if(valid2(nums, 1)) pre2++;
        if(nums.charAt(1)!='0') pre2++;
        for(int i=2;i<nums.length();++i){
            int cur = 0;
            if(nums.charAt(i)!='0') cur = pre2;
            if(valid2(nums, i)) cur+=pre1;
            pre1 = pre2;
            pre2 = cur;
        }
        return pre2;
    }
    
    private boolean valid2(String nums, int i){
        char c = nums.charAt(i-1);
        if(c=='0') return false;
        if(c<='1') return true;
        if(c=='2' && nums.charAt(i)<='6') return true;
        return false;
    }
}