復号方法(アルファベットA-Zを含むメッセージは、以下のように符号化される)
アルファベット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 2 6)に復号することができる.
解題構想:フィボナッチシーケンスに非常に類似しており、dp[i]=dp[i-1]+dp[i-2]と理解できる.しかし、これは条件があります.
iを下付き文字列とし、i−1ビットとiビットからなる2桁が10−26でない場合、dp[i−2]は加算されない.iを下付きとする要素が0である、dp[i-1]を加えることもできない.
数値のみを含む空でない文字列を指定します.復号方法の合計数を計算します.
例1:入力:「12」出力:2説明:「AB」(1 2)または「L」(12)に復号できる.
例2:入力:「226」出力:3説明:「BZ」(2 26)、「VF」(22 6)、または「BBF」(2 2 2 6)に復号することができる.
解題構想:フィボナッチシーケンスに非常に類似しており、dp[i]=dp[i-1]+dp[i-2]と理解できる.しかし、これは条件があります.
iを下付き文字列とし、i−1ビットとiビットからなる2桁が10−26でない場合、dp[i−2]は加算されない.iを下付きとする要素が0である、dp[i-1]を加えることもできない.
public class test0511 {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.numDecodings("101"));
}
}
class Solution {
public int numDecodings(String s) {
if(s.length() == 0 || s.charAt(0) =='0' ){
return 0;
}
if(s.length() == 1 ){
return 1;
}
int dp1 = 1;// dp[i-2]
int dp2 = 1;// dp[i-1]
int result = 0;
for(int i = 1;i=10 && i1 <=26 ){
result = dp1;
}
if(s.charAt(i) != '0'){
result += dp2;
}
dp1 = dp2;
dp2 = result;
result = 0;
}
return dp2;
}
}