LeetCode: 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 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.

---

We can use dynamic programming to solve this problem. Assume dp[i] is the number of decoding ways until s[i]. If the current char s[i] is 0 and previous char is neither 1 nor 2, then we can return 0 directly. If previous char is 1 or 2, then dp[i] will be equal to dp[i-2]. If the number constructed from s[i] and s[i-1] is between 11 and 26, then dp[i] = dp[i-1] + dp[i-2]. Otherwise dp[i] = dp[i-1].

C++ Code:

/*
 * func: num_decoding
 * goal: find the total number of ways to decode
 * @param s: input string s
 * return: total ways
 */
/*
 * DP is used. dp_helper[i] stands for the number of ways until s[i-1]
 * complexity: time O(n), space O(n)
 */
int num_decoding(string s){
    if(s.length() == 0 || s[0] == '0'){
        return 0;
    }
    vector<int> dp_helper(s.length()+1, 1);
    
    for(int i = 1; i < s.length(); ++i){
        string substring = s.substr(i-1, 2);
        int x = atoi(substring.c_str());
        if(x >= 10 && x <= 26){
            if(x == 10 || x == 20)
                dp_helper[i+1] = dp_helper[i-1];
            else
                dp_helper[i+1] = dp_helper[i-1] + dp_helper[i];
        }else if(s[i] == '0'){
            return 0;
        }else{
            dp_helper[i+1] = dp_helper[i];
        }
    }
    
    return dp_helper[s.length()];
}

Python Code:

# func: find the number of ways to decode numbers
# @param s: input string
# @return: number of ways
# complexity: time O(n), space O(n)
def num_decoding(s):
    if len(s) == 0 or s[0] == '0':
        return 0

    dp_helper = [1] * (len(s)+1)

    for i in xrange(1, len(s)):
        substr = s[i-1] + s[i]
        if 10 <= int(substr) <= 26:
            if int(substr) == 10  or int(substr) == 20:
                dp_helper[i+1] = dp_helper[i-1]
            else:
                dp_helper[i+1] = dp_helper[i-1] + dp_helper[i]
        elif s[i] == '0':
            return 0
        else:
            dp_helper[i+1] = dp_helper[i]

    return dp_helper[len(s)]