Problem description:

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 a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

1
2
Input: "12"
Output: 2

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

1
2
Input: "226"
Output: 3

Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Solution:

example:

1
2
3
4
5
6
7
8
9
10
11
1. basic case:
 "3"-> c, num_ways("3")= 1
 ""-> "", num_ways("")= 1

2. common cases:
 "12345", num_ways("2345")+num_ways("345")

 "27345", nums_ways("7345")

3. exception:
 "011", num_ways("011")= 0

Use a dp array of size n + 1 to store the subproblem solutions.
dp[0] means an empty string will have one way to decode.
dp[1] means the way to decode a string of size 1.

For other cases, check one digit(dp[i-1]) and two digit(dp[i-2]) combination and save the results along the way. In the end, dp[n] will be the end result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def numDecodings(self, s: str) -> int:
        # decode ways is determined by how many characters, so empty string should count as well
        dp = [0]* (len(s)+1)
        dp[0] = 1
        dp[1] = 0 if s[0] == "0" else 1
        
        for i in range(2, len(dp)):
            num1 = int(s[i-1:i])
            num2 = int(s[i-2:i])
            if num1 > 0 and num1 <= 9:
                dp[i] += dp[i-1]
            if num2 >= 10 and num2 <= 26:
                dp[i] += dp[i-2]
        return dp[-1]
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
class Solution {
public:
    int numDecodings(string s) {
        /*
        use 1d dp array to sum up how many ways from beginning
        dp[i-1]: 1 digit: can not be zero 
        dp[i-2]: 2 digits: can not exceed 26, digit of ten can not be zero
        */
        int n= s.length();
        if(!n) return 0;
        vector<int> dp(n+1, 0);
        dp[0]= 1; //empty string only one way to decode
        
        //since the dp equation needs dp[i-1] and dp[i-2] to calculate
        //we also need to init dp[1]
        dp[1]= s[0] == '0'? 0:1; 
        
        for(int i= 2; i< dp.size(); i++){
            int n1= stoi(s.substr(i-1, 1));
            //cout<<n1<<endl;
            int n2= stoi(s.substr(i-2, 2));
            //cout<<n2<<endl<<endl;
            
            if(n1>= 1 && n1 <= 9) dp[i]+= dp[i-1];
            if(n2>= 10 && n2 <= 26) dp[i]+= dp[i-2];
        }
        return dp[n];
    }
};

time complexity: $O(n)$
space complexity: $O(n)$

reference:
https://leetcode.com/problems/decode-ways/discuss/253018/Python%3A-Easy-to-understand-explanation-bottom-up-dynamic-programming