LintCode刷题——解码方法

题目描述：

有一个消息包含A-Z通过以下规则编码

'A' -> 1
'B' -> 2
...
'Z' -> 26

现在给你一个加密过后的消息，问有几种解码的方式

样例：

给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2

算法分析：

'A'到'Z' 26个字母最多2位最少1位且不为0，因此存在多种解码的可能性。建立一维数组DP[i]表示到当前第i位字符时所能解码的方式，因此对于某一位i，若其不为‘0’，则DP[i] += DP[i-1],若其能与i-1位构成的数字在1到26之间，则DP[i]+=DP[i-2]。因此动态规划表达式为：

　　　　①S[i]!=0：DP[i] = DP[i-1] + (S[i-1]=='1'||S[i-1]=='2'&&S[i]<='6')?DP[i-2]:0；

　　　　②S[i]=0：DP[i] = (S[i-1]=='1'||S[i-1]=='2')?DP[i-1]:0；

要注意的一点是在进行二位数判断时直接用字符进行判断即可，Integer.valueOf()反而会增加代码量如对前一位是‘0’的处理等等；

代码：

public class Solution {
    /*
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    public int numDecodings(String s) {
        // write your code here
        int length = s.length();
        //对首位0或空字符串进行处理
        if(length==0||s.charAt(0)=='0'){
            return 0;
        }
        int[] result = new int[length+1];
        result[0] = 1;
        result[1] = 1;
        for(int i=1;i<length;i++){
            //遇到0时的处理方式
            result[i+1]=s.charAt(i)=='0'?0:result[i];
            //判断数字是否在范围内
            if(s.charAt(i-1)=='1'||s.charAt(i-1)=='2'&&s.charAt(i)<='6'){
                result[i+1]+=result[i-1];
            }
        }
        return result[length];
    }
}