解码方法

一条包含字母 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)

思路：

运用递归的思想当前值为1种当前值如果能和下一个值组成小于26的数又是一种递归

public int numDecodings1(String s) {
        char[] arr= s.toCharArray();
        return process(arr,0,arr.length-1);
    }
    public static int process(char[] arr,int i,int end){
        if(i<=end&&arr[i]=='0')  return 0; //以0开头  无此种编码
        if(i>=end) return 1;
        int val=arr[i];
        if(val=='2'&&i+1<=end&&arr[i+1]<='6'){
            return process(arr,i+1,arr.length-1)+process(arr,i+2,arr.length-1);
        }
        if(val=='1'&&i+1<=end&&arr[i+1]<='9'){
            return process(arr,i+1,arr.length-1)+process(arr,i+2,arr.length-1);
        }
        return process(arr,i+1,arr.length-1);
    }

做完之后，发现重复计算太多改进用map保存已经计算过的 key为从当前i位置开始到结束 value为最大解码数

贴代码：

递归  key为从当前i位置开始到结束  value为最大解码数
public int numDecodings2(String s) {
        char[] arr= s.toCharArray();
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        return process1(arr,0,arr.length-1,map);
    }
    public static int process1(char[] arr,int i,int end,HashMap<Integer,Integer> map){
        if(i<=end&&arr[i]=='0')  return 0;
        if(i>=end) return 1;
        if(map.containsKey(i)){
	return map.get(i);
        }
        int val=arr[i];
        if(val=='2'&&i+1<=end&&arr[i+1]<='6'){
            int res=process(arr,i+1,arr.length-1,map)+process(arr,i+2,arr.length-1,map);
            map.put(i,res);
		return res;
        }
        if(val=='1'&&i+1<=end&&arr[i+1]<='9'){
             int res=process(arr,i+1,arr.length-1,map)+process(arr,i+2,arr.length-1,map);
             map.put(i,res);
             return res;
        }
        int res= process(arr,i+1,arr.length-1,map);
        map.put(i,res);
         return res;
    }

对开头为1和2的情况进行合并

 public int numDecodings3(String s) {
        char[] arr= s.toCharArray();
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        return process3(arr,0,arr.length-1,map);
    }
    public static int process3(char[] arr,int i,int end,HashMap<Integer,Integer> map){
        if(i<=end&&arr[i]=='0')  
        	return 0;
        if(i>=end) 
        	return 1;
        if(map.containsKey(i)){
	        return map.get(i);
        }
        int res=0;    //将a[i]等于1和2的情况合并
        if(i+1<=end&&((arr[i]-'0')*10+(arr[i+1]-'0'))<=26){
           res= process3(arr,i+1,arr.length-1,map)+process3(arr,i+2,arr.length-1,map);
           map.put(i,res);
            return res;
       
    }
        res= process3(arr,i+1,arr.length-1,map);
        map.put(i,res);
        return res;
    }