A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
按照题目中的规则，给定一个字符串，然后判断有多少种原始的组合方式。
1、基本方法是用动态规划，很容易想到，如果i>2,同时num[i-1]与num[i]这两个数字是在11-26之间，那么dp[i] = dp[i-1]+dp[i-2]
2、容易出错的点在于对于0的判断，如果0开头，那么直接返回0，还有就是如果num[i]==0的时候，需要根据num[i-1]的值判断是该返回0，还是dp[i] = dp[i-2]。
其实这道题这样就已经做完了，但是
3、我先是看到了输入是String而不是int[]，我以为输入中是可以带有字母的，而我用字母测试的时候，也是通过的。所以我的做法中带入了判断字母的部分，所以最后结果是2ms，并不是最快的1ms。
public class Solution {
public int numDecodings(String s) {
int len = s.length();
if( len == 0)
return 0;
else if( len == 1)
return s.charAt(0) == '0'?0:1;
int[] num = new int[len];
for( int i = 0;i<len;i++){
if( s.charAt(i) >= '0' && s.charAt(i) <='9')
num[i] = s.charAt(i)-'0';
else
num[i] = -1;
}
for( int i = 0;i <len ;i++)
num[i] = s.charAt(i)-'0';
int[] dp = new int[len];
if( num[0] == 0)
return 0;
else
dp[0] = 1;
if( num[1] == 0){
if( (num[0] >2 || num[0]<1) )
return 0;
else
dp[1] = 1;
}else if( (num[0] == 1 && num[1] > 0) || (num[0] == 2 && num[1]<7 && num[1] > 0))
dp[1] = 2;
else
dp[1] = dp[0];
for( int i = 2;i<len;i++){
if( num[i] == 0){
if( num[i-1] >2 || num[i-1] < 1 )
return 0;
else
dp[i] = dp[i-2];
}
else if( (num[i-1] == 1 && num[i] > 0) || (num[i-1] == 2 && num[i] < 7 ))
dp[i] = dp[i-1]+dp[i-2];
else
dp[i] = dp[i-1];
}
return dp[len-1];
}
}
下面是discuss中的某个代码，并没有判断字母。
public class Solution {
public int numDecodings(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1 : 0;
for(int i = 2; i <= n; i++) {
int first = Integer.valueOf(s.substring(i-1, i));
int second = Integer.valueOf(s.substring(i-2, i));
if(first >= 1 && first <= 9) {
dp[i] += dp[i-1];
}
if(second >= 10 && second <= 26) {
dp[i] += dp[i-2];
}
}
return dp[n];
}
}