1、前言

2、思路

这道题的思路跟爬楼梯简直是一摸一样，但是跳台阶的处理比较简单，到了最后直接返回 0 或者 1即可。这边针对两个字符的情况，需要判断一下是否小于等于26。

3、代码

class Solution {
    public int numDecodings(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        
        int[] memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return dfs(s, 0, memo);
    }

    private int dfs(String s, int start, int[] memo){
        if(start == s.length()){
            return 1;
        }

        if(s.charAt(start) == '0'){
            return 0;
        }

        if(memo[start] != -1){
            return memo[start];
        }

        int ans1 = dfs(s, start + 1, memo);
        int ans2 = 0;
        if(start < s.length() - 1){
            int ten = (s.charAt(start) - '0') * 10;
            int one = s.charAt(start + 1) - '0';
            if(ten + one <= 26){
                ans2 = dfs(s, start + 2, memo);
            }
        }
        memo[start] = ans1 + ans2;

        return memo[start];
    }
}