Total Number of Ways to Decode the Message via Dynamic Programming Algorithm

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

Dynamic Programming

The tricky part of the DP equation is to deal with the invalid cases where there are zeros. For example, 0, 0001, 30, 2005. All these inputs result in zeros because you just can’t decode the message if there are zeros other than the forms of 10 or 20.

The edge cases would be zeros in the middle, the leading zeros, and the empty input. If we use f(x) to denote the number of ways up to x-th character. We have f(x) = f(x – 1) + f(x – 2) the fibonacci subject to the validity checks.

If we have S[x] is ‘0’, we have to check its previous digit, if it is more than 2 or it is ‘0’, we immediately know it is zero because you can’t use previous digit to form a valid case and neither you can start with ‘0’. If the previous digit is ‘1’ or ‘2’, we know we can make a valid case by either 10, or 20, then the answer will be the same as f(x – 2).

If the previous number is zero, f(i) = f(i – 1). because we can’t use the previous digit to form the current group. If two-digit number S[i-1]S[i] is less or equal than 26, we have another f(x-2) solutions.

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

class Solution {
public:
    int numDecodings(string s) {
        const int n = s.length();
        int64_t f[n + 1];        
        if (n == 0) return 0;
        if (s[0] == '0') return 0;        
        if (n == 1) return 1;
        if (s[1] == '0' && s[0] >= '3') return 0;
        f[0] = 1;
        std::function<int(int)> F = [&s](int i) {
            return ((s[i] - '0') * 10 + s[i + 1] - '0');                        
        };
        f[1] = F(0) <= 26 ? 2 : 1;
        if (s[1] == '0') f[1] = 1;
        for (int i = 2; i < n; ++ i) {
            if (s[i] == '0') {
                if (s[i - 1] >= '3' || s[i - 1] == '0') {
                    return 0;
                }
                f[i] = f[i - 2];
            } else {
                f[i] = f[i - 1];
                if (s[i - 1] > '0') {         
                    if (F(i - 1) <= 26) {
                        f[i] += f[i - 2];
                    }                    
                }
            }
        }        
        return f[n - 1];
    }
};

class Solution {
public:
    int numDecodings(string s) {
        const int n = s.length();
        int64_t f[n + 1];        
        if (n == 0) return 0;
        if (s[0] == '0') return 0;        
        if (n == 1) return 1;
        if (s[1] == '0' && s[0] >= '3') return 0;
        f[0] = 1;
        std::function<int(int)> F = [&s](int i) {
            return ((s[i] - '0') * 10 + s[i + 1] - '0');                        
        };
        f[1] = F(0) <= 26 ? 2 : 1;
        if (s[1] == '0') f[1] = 1;
        for (int i = 2; i < n; ++ i) {
            if (s[i] == '0') {
                if (s[i - 1] >= '3' || s[i - 1] == '0') {
                    return 0;
                }
                f[i] = f[i - 2];
            } else {
                f[i] = f[i - 1];
                if (s[i - 1] > '0') {         
                    if (F(i - 1) <= 26) {
                        f[i] += f[i - 2];
                    }                    
                }
            }
        }        
        return f[n - 1];
    }
};

Time complexity is O(N) and the space complexity is O(N). We define in above solution, a function variable using std::function, that can be used as local function, to compute the values given a index of the string.

1
2
3

std::function<int(int)> F = [&s](int i) {
   return ((s[i] - '0') * 10 + s[i + 1] - '0');                        
};

std::function<int(int)> F = [&s](int i) {
   return ((s[i] - '0') * 10 + s[i + 1] - '0');                        
};

The Dynamic Programming algorithm stores the intermediate results in the array, which speeds up the computation. You could use Depth First Search algorithm although, which might be a bit slower.

–EOF (The Ultimate Computing & Technology Blog) —