【leetcode】No.91：decode-ways

题目描述

一条仅包含字母‘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];
    }
}