使用动态规划的方法,但是其实不需要使用数组来保存所有的位置的情况,可以优化后,只用两个值保存前面两个字符的情况即可。

因为本题其实可以简化成“跳台阶”问题,就是可以是一步或者两步,只不过需要加些条件来处理而已



public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        //用来保留前面两个字符位置对应的可能译码结果数
        int first = 1, second = 1;
        for(int i = 0;i < nums.length();i++){
            //遇到0不能译码,second清零
            if(nums.charAt(i) == '0'){
                second = 0;
            }
            //更新前两个字符对应的值
            //符合条件则可以译1个或者2个数字
            if(i >= 1 && Integer.parseInt(nums.substring(i-1,i+1)) <= 26){
                second = first + second;
                first = second - first;
            }
            //只能译1个数字
            else{
                first = second;
            }
        }
        return second;
    }
}

时间复杂度O(n),空间复杂度O(1),只多用了两个变量来保存数值