Medium

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.

FB的高頻題，老師以climbing stairs引出來(lái)的，會(huì)了就比較簡(jiǎn)單。有幾個(gè)地方要注意以下：

• 方便表達(dá)，用dp[i]表示到達(dá)所給串的第i個(gè)字符時(shí)，一共有的decode的方法， dp[0]表達(dá)的是字符串是空的時(shí)候可以decode的方法數(shù)（1種而不是0種），而不是達(dá)到s.charAt(0)時(shí)候的方法數(shù)
• 判斷s.charAt(0) == 0?, 如果等于，其實(shí)是不可能出現(xiàn)的情況，方法數(shù)為零，也可以直接返回0了。
• for循環(huán)從i = 2開(kāi)始，因?yàn)槲覀儚膁p[2]開(kāi)始求。 dp[2]表達(dá)的是到達(dá)第二個(gè)字符串一共能decode的方法總數(shù)。那么我們就需要看當(dāng)前字符串構(gòu)成的一位數(shù)和前一個(gè)字符串加上當(dāng)前字符串構(gòu)成的二位數(shù)即s[1], s[0,1], 也就是s.substring(i - 1, i)和s.substring(i - 2, i)， 分別看前者是不是在[1, 9]范圍里，后者是不是在[10,26]范圍里，如果是，就dp[i] += dp[i - 1]或dp[i] += dp[i - 2].

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' ? 0 : 1;
        for (int i = 2; i <= s.length(); i++){
            int prevOne = Integer.valueOf(s.substring(i - 1, i));
            int prevTwo = Integer.valueOf(s.substring(i - 2, i));
            if (prevOne > 0 && prevOne <= 9){
                dp[i] += dp[i - 1];
            }
            if (prevTwo >= 10 && prevTwo <= 26){
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}