91. Decode Ways

一、题目

　　1、审题

　　2、分析

　　　　每个字母对应一个数字编码，eg 

　　　　A -->1

　　　　B -->2

　　　　...

　　　　Z --> 26

　　　　给出一串数字，求可以解码成的共多少中字符可能。

二、解答

　　1、思路：

　　　　采用递推数组进行记录。

public int numDecodings2(String s) {
        
        if(s == null || s.length() == 0 || s.startsWith("0") || s.contains("00"))
            return 0;
        
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        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];
        
    }