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