Description

Decode Ways

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).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Solution

 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
30
31
32
33
34

func numDecodings(s string) int {
    if len(s) == 0 || s[0] == '0' {
        return 0
    }

    dp := make([]int, len(s)+1)
    dp[0] = 1
    dp[1] = 1

    for i := 1; i < len(s); i++ {
        if s[i] == '0' {
            if s[i-1] == '1' || s[i-1] == '2' {
                // if this number is '0'
                //  the previous number must be '1' or '2'
                //  and the previous solution(dp[i]) should return to dp[i-1]
                //  dp[i] = dp[i-1]
                dp[i+1] = dp[i-1]
            } else {
                return 0
            }
        } else if s[i-1] == '1' || (s[i-1] == '2' && s[i]-'0' <= 6) {
            // if this number is not '0'
            //   like 226, when i is 2, number is 6
            //   it can be splitted as "2|26" or "22|6"
            //   so it can be from [2] and [22]
            dp[i+1] = dp[i] + dp[i-1]
        } else {
            // else there is only one way
            dp[i+1] = dp[i]
        }
    }

    return dp[len(s)]
}