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.

Solution: Dynamic Programming

This problem is quite similar to climbing stairs, except that it has many edge cases. You need to consider those edge cases before start coding.

Let's create an array of integers, arr[i] represents the number of ways to decode substr(0..i-1). There are two cases we need to consider:

1. If s[i-1] != '0', then arr[i] = arr[i-1]
2. If s[i-2] == '1', or s[i-2] == '1' and s[i-1] <= '6', then arr[i] += arr[i-2]

We can build the array from bottom up.

Time complexity O(n) and space complexity O(n)

int numDecodings(string &s) {
        // write your code here
        if (s.empty()) return 0;

        int arr[s.size()+1] = {0};
        arr[0] = 1;
        arr[1] = (s[0] == '0') ? 0 : arr[0];

        for (int i = 2; i <= s.size(); ++i) {
            arr[i] = (s[i-1] == '0') ? 0 : arr[i-1];

            if (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) {
                arr[i] += arr[i-2];
            }
        }
        return arr[s.size()];
    }

Solution: Optimized

Like climbing stairs and fibonnaci numbers, we only need to store the previous two result.

    int numDecodings(string &s) {
        if (s.empty() || s.front() == '0') return 0;
        int c1 = 1, c2 = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == '0') c1 = 0;
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
                c1 = c1 + c2;
                c2 = c1 - c2;
            } else {
                c2 = c1;
            }
        }
        return c1;
    }