91.解码方法

题目描述

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例：

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

思路

1.这道题可以使用动态规划思想求解，而动态规划的套路都是一致的，先暴力递归求解，然后使用备忘录方法避免重复求解同一子问题，最后自底向上的找到状态转移方程求解。
2.当两位数小于27时状态转移方程为dp[i] = dp[i+1]dp[i+2]；否则为dp[i] = dp[i+1]。

递归代码实现

   public int numDecodings(String s) {
        return numDecodings(s,0);
    }

    private int numDecodings(String s, int start){
        if(start == s.length()){
            return 1;
        }
        if(s.charAt(start) == '0'){
            return 0;
        }
        int ans1 = numDecodings(s,start+1);
        int ans2 = 0;
        if(start < s.length() - 1){
            int cur = Integer.parseInt(s.substring(start,start+2));
            if(cur <= 26){
                ans2 = numDecodings(s,start+2);
            }
        }
        return ans1 + ans2;
    }

备忘录代码实现

public int numDecodings(String s) {
        Map<Integer,Integer> map = new HashMap<>();
        return numDecodings(s,0,map);
    }

    private int numDecodings(String s, int start, Map<Integer,Integer> map){
        if(start == s.length()){
            return 1;
        }
        if(s.charAt(start) == '0'){
            return 0;
        }
        int res = map.getOrDefault(start,-1);
        if(res != -1)
            return res;
        int ans1 = numDecodings(s,start+1,map);
        int ans2 = 0;
        if(start < s.length() - 1){
            int cur = Integer.parseInt(s.substring(start,start+2));
            if(cur <= 26){
                ans2 = numDecodings(s,start+2,map);
            }
        }
        map.put(start,ans1 + ans2);
        return ans1 + ans2;
    }

动态规划代码实现

    public int numDecodings(String s) {
        int[] dp = new int[s.length()+1];
        dp[s.length()] = 1;
        if (s.charAt(s.length() - 1) != '0') {
            dp[s.length() - 1] = 1;
        }
        for (int i = s.length()-2; i >=0; i--) {
            if(s.charAt(i) == '0')
                continue;
            int cur = Integer.parseInt(s.substring(i,i+2));
            if(cur<=26)
                dp[i] = dp[i+1] + dp[i+2];
            else
                dp[i] = dp[i+1];
        }
        return dp[0];
    }