dustfree's blog
0%

Decode Ways

Posted on In ,

Question

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

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: “12”
Output: 2
Explanation: It could be decoded as “AB” (1 2) or “L” (12).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
@param: String
@return: int
Algorithm: dp[i]表示i个字符的解码总数
1. 如果当前字符是1~9 则可以单独解码 dp[i] += dp[i-1];
2. 如果当前字符是10~26则可以2位一起解码 dp[i] += dp[i-2];
*/
public int numDecodings(String s) {
    if (s.length() == 0) return 1;
    int[] dp = new int[s.length()+1];
    
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    
    for (int i = 2; i <= s.length(); i++) {
        int one = Integer.valueOf(s.substring(i-1,i));
        int two = Integer.valueOf(s.substring(i-2,i));
        if (one >= 1 && one <= 9) dp[i] += dp[i-1];
        if (two >= 10 && two <= 26) dp[i] += dp[i-2];            
    }
    return dp[s.length()];
}