237、解码方法

题目描述：
一条包含字母 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) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

用递归撸了个超时的代码，难受…

class Solution {
      public int numDecodings(String s) {
      if(Integer.valueOf(s.substring(0,1)) == 0){
	        	return 0;
	        }
          Set<String> set = new HashSet<>();
        List<String> list = new ArrayList<>();
        get(0,s,set,list);
        return set.size();
    }
   public void get(int index,String s,Set<String> set,List<String> list){
	        if(index >= s.length()){
	            StringBuilder builder = new StringBuilder();
	            for (String s1 : list) {
	                builder.append(s1);
	            }
	            if(!set.contains(new String(builder)) && isva(new String(builder))){
	                set.add(new String(builder));
	            }
	            return;
	        }
	        int  get =  Integer.valueOf(s.substring(index,index + 1));
	        if(get == 0){
	        	return ;
	        }
//	            尝试加两个
	            int j = index + 2;
	            if(j <= s.length()){
	               int gettwo =  Integer.valueOf(s.substring(index,j));
	                if(gettwo < 27){
	                    list.add(new String( "" + (char)('a' + (gettwo - 1))));
	                    get(index + 2,s,set,list);
	                    list.remove(list.size() - 1);
	                }
	                 
	            }
	                  list.add(new String( "" + (char)('a' + (get - 1))));
	                  get(index + 1,s,set,list);
	        }
    public boolean isva(String tem){
	    	char tems[] =tem.toCharArray();
	    	for (char c : tems) {
				if(c < 'a' || c > 'z'){
					return false;
				}
			}
	    	return true;
	    }

}

看看别人实现的，使用动态规划

class Solution {
      public int numDecodings(String str) {
       int len = str.length();
        if(len == 0 || (len == 1 && str.charAt(0) == '0'))
            return 0;
        int[] dp = new int[2];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 0; i < len;i++){
            int temp = 0;
            if(str.charAt(i) != '0') 
                temp += dp[1];
            if(i > 0 && (str.charAt(i-1) == '1' || (str.charAt(i-1) == '2' && str.charAt(i) <= '6')))
                temp += dp[0];
            dp[0] = dp[1];
            dp[1] = temp;
        }
        
        return dp[1];
    }

}

自己的思路：

class Solution {
      public int numDecodings(String s) {
      int []dp = new int[2];
        dp[0] = 1;
        dp[1] = 1;
        if(s.charAt(0) == '0'){
            return 0;
        }
        for (int i = 1; i < s.length(); i++) {
                char tem1 = s.charAt(i - 1);
                char tem2 = s.charAt(i);
                if(tem2 == '0' ){
                    if(tem1 == '0' || tem1 > '2'){
                        return 0;
                    }else{
                        dp[1] = dp[0];
                    }
                }else{
                    if(tem1 == '1' || ((tem1 == '2' && tem2 <= '6'))){
                        int tem = dp[0];
                        dp[0] = dp[1];
                        dp[1] = dp[1] + tem;
                    }else{
                        dp[0] = dp[1];
                        dp[1] = dp[0];
                    }
                }
        }
        return dp[1];
    }

}