91.解碼方法

一條包含字母 A-Z 的消息通過以下方式進行了編碼：
'A' -> 1
'B' -> 2
...
'Z' -> 26
給定一個只包含數(shù)字的非空字符串，請計算解碼方法的總數(shù)。
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：動態(tài)規(guī)劃
如果沒有1到26的數(shù)字限制，我們很容易把這個問題聯(lián)想到爬樓梯的那個問題。dp[i]=dp[i-1]+dp[i-2]。而現(xiàn)在有一些情況，使得只剩1個數(shù)（末位為0）不成立；有一些情況，使得2位數(shù)不成立（>26或者以0開頭的2位數(shù)）。我們需要判斷這些情況

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()];
    }
}