A message containing letters from A-Z is being encoded to numbers using the following mapping:

1
2
3
4
'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.

这种题目也挺恶心的，就是分情况讨论，先把情况分的细一点没关系，最后可以把条件合并
譬如说可以分成

  1. 00 这种情况不可能，真接return 0
  2. 01 - 09 这种情况0只能跟前面的配. dp[i] = dp[i - 1]
  3. 10 10只能配在一起 dp[i] = dp[i - 2]
  4. 11 - 19 十位即可以跟前面的配，也可以跟后面的配. dp[i] = dp[i - 1] + dp[i - 2]
  5. 20 20只能配在一起 dp[i] = dp[i - 2]
  6. 21 - 26 十位即可以跟前面的配，也可以跟后面的配. dp[i] = dp[i - 1] + dp[i - 2]
  7. 27+ 这种情况，十位只能跟前面的配. dp[i] = dp[i - 1]
  8. 30, 40, …. 这种情况不可能，return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int numDecodings(String s) {
    if (s == null || s.length() == 0 || s.charAt(0) == '0')
        return 0;
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i < s.length() + 1; i++) {
        int tens = Integer.parseInt(s.substring(i - 2, i));
        if (tens % 10 == 0) {
            if (tens == 0 || tens >= 30)
                return 0;
            else
                dp[i] = dp[i - 2];
        } else {
            if (tens > 0 && tens < 10) {
                dp[i] = dp[i - 1];
            } else if (tens > 10 && tens <= 26) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
    }
    return dp[s.length()];
}