LeetCode91. デコード方法

1432 ワード

A-Zのアルファベットを含むメッセージは、次のルールによって符号化されます.
'A' -> 1
'B' -> 2
...
'Z' -> 26

数値を含む符号化メッセージを指定し、復号方法の合計数を決定します.
例えば、所与のメッセージは"12"であり、"AB"(1 2)または"L"(12)に復号することができる."12"の復号方法は2種類である.
考え方:
動的計画の問題と見なすことができます
まず、1番目のビットが0であれば、符号化を変えることができず、0を返す.
次に、トランスコードするたびに、i位とi-1位の数字が26以下であるかどうかを見ることができ、一致すれば、i-2位で復号します.i番目のビットが0に等しくなければ、i番目のビットで復号することに相当する.両方が一致する場合、dp[i]=dp[i-1]+dp[i-2]に相当する.
コード:
二桁の場合、間違えてしまうのは面倒です. 
    public static int numDecodings(String s) {
        if(s.length()==0){
            return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = s.charAt(0)=='0'?0:1;
        if(s.length()==1){
            return dp[0];
        }
        int k = s.charAt(0) > '0' && s.charAt(1) > '0'? 1:0;
        dp[1] = k + (s.charAt(0) == '1' || s.charAt(0) == '2' && s.charAt(1) <= '6' ? 1:0);
        for (int i = 2; i < dp.length; i++) {
            if(s.charAt(i)!='0'){
                dp[i] += dp[i-1];
            }
            if(s.charAt(i-1)=='1'||s.charAt(i-1)=='2'&&s.charAt(i)<='6'){
                dp[i] += dp[i-2];
            }
        }
        return dp[s.length()-1];
    }