91.解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
https://leetcode-cn.com/problems/decode-ways/
思路
思路一：dfs。不合条件的就放弃这条路径
缺点：会有重复计算。所以效率不是很好。

image.png

class Solution {
    //ArrayList<String>() list = new ArrayList<String>();
    int count =0;
    public int numDecodings(String s) {
        char[] charArray = s.toCharArray();
        dfs(charArray,0);
        return count;
    }
    public void dfs(char[] charArray,int start){
        if(start>=charArray.length)return;
        if(start==charArray.length-1){
            if(isOk(charArray,start,start)){
                count++;
            }
            return;
        }else if(start==charArray.length-2){
            if(isOk(charArray,start,start+1)){
                count++;
            }
            if(isOk(charArray,start,start)){
                dfs(charArray,start+1);
            }
        }else{
            if(isOk(charArray,start,start)){
                dfs(charArray,start+1);
            }
            if(isOk(charArray,start,start+1)){
                dfs(charArray,start+2);
            }
        }
    }
    public boolean isOk(char[] charArray,int start,int end){
        if(end>=charArray.length||start>=charArray.length){
            return false;
        }
        if(start==end){
            return charArray[start]!='0';
        }else{
            switch(charArray[start]){
                case '1':
                    return true;
                case '2':
                    return charArray[end]<='6'&&charArray[end]>='0';
                default:
                    return false;
            }
        }
    }
}

思路2：动态规划
如果没有1到26的数字限制，我们很容易把这个问题联想到爬楼梯的那个问题。dp[i]=dp[i-1]+dp[i-2]。而现在有一些情况，使得只剩1个数（末位为0）不成立；有一些情况，使得2位数不成立（>26或者以0开头的2位数）。我们需要判断这些情况

class Solution {
    public int numDecodings(String s) {
        if(s.length()==0||s.charAt(0)=='0')return 0;
        char[] charArray = s.toCharArray();
        int[] dp = new int[s.length()+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=1;i<=s.length()-1;i++){
            int temp = Integer.valueOf(s.substring(i-1,i+1));
            //两位
            if(temp<=26&&temp>=10){
               dp[i+1]+=dp[i-1]; 
            }
            //1位
            if(temp%10!=0){
                dp[i+1]+=dp[i];
            }
        }
        return dp[s.length()];
    }
}