题目描述
一条仅包含字母‘A’-‘Z’的消息用下列的方式加密成数字
'A' -> 1
'B' -> 2
...
'Z' -> 26
现在给出加密成数字的密文，请判断有多少种解密的方法
例如：
给出的密文为“12”，可以解密为"AB"(1 2) 或者"L"(12).
所以密文"12"的解密方法是2种.
思路：
dp[i]表示前i个字符可以编码的情况总数，dp[0]=1，如果当前第i位能与i-1位组合成一个10~26的数字，则dp[i]=dp[i-1]+dp[i-2]，否则dp[i]=dp[i-1]，注意两个特殊点：
如果当前位为0，则只能和前面组合，如果不能组合，则无法解密
如果第一位就为0，直接返回0即可
代码：
public class Solution {
public int numDecodings(String s) {
if (s.isEmpty()) return 0;
char[] str = s.toCharArray();
int len = s.length();
int[] dp = new int[len+1];
dp[0]=1;
dp[1] = str[0]=='0'?0:1;
for (int i=1; i<len; i++){
int value = (str[i-1]-'0')*10+(str[i]-'0');
if (str[i]-'0'==0){
if (value<=26&&value>=10) dp[i+1]=dp[i-1];
else return 0;
}
else{
if (value<=26&&value>=10) dp[i+1] = dp[i-1] + dp[i];
else dp[i+1] = dp[i];
}
}
return dp[len];
}
}
