leetcode解题: Decode Ways (91)

发表于 | 分类于

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.

解法1：DP O(N) with O(1) 空间

典型DP, dp数组表示前i个数字的# of decode ways. 那么对于dp[i], 他存在decode的办法有两种：

  1. 单独一个数字decode, 这种情况实际是dp[i -1]
  2. 和嵌挤一个数字拼成一个10 ~ 26 的数字decode, 这种情况的办法是dp[i - 2]
    但是要注意的是对于每一种可能的decode办法，有corner case需要考虑：
  3. 如果第i个数是0，那么只可能是dp[i - 2],并且要检查i - 1 和i拼成的数是否在10 ~ 26范围内, 比如120只可能是[1, 20]的分割
  4. 检查数是否在10 ~ 26范围内
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
29
public int numDecodings(String s) {
	
    if (s == null || s.length() == 0) {
        return 0; // empty string has no way of decoding
    }
    
    int[] dp = new int[s.length()];
    
    dp[0] = s.charAt(0) == '0'?0: 1;
    
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) != '0') {
            dp[i] = dp[i - 1];
        }
        
        int temp = Integer.parseInt(s.substring(i - 1, i + 1));
        if (temp >= 10 && temp <= 26) {
            if (i == 1) {
                dp[i] += 1;
            } else {
                dp[i] += dp[i - 2];
            }
        }
        if (dp[i] == 0) {
            return 0;
        }
    }
    return dp[s.length() - 1];    
}