Blind 75.24 - Decode Ways

Decode ways.

Problem description

Taken directly from LeetCode.

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = “12”
Output: 2
Explanation: “12” could be decoded as “AB” (1 2) or “L” (12).

Example 2:

Input: s = “226”
Output: 3
Explanation: “226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Example 3:

Input: s = “06”
Output: 0
Explanation: “06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”).

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Solution type

Caching via DP.

Solution

The recurrence relation seems obvious conceptually: the number of ways to encode \(n\) letters is the sum of the number of ways to encode \(n - 1\) characters (where the remaining character has to map to a valid letter) plus the number of ways to encode \(n - 2\) characters (where the remaining two characters combined have to map to a valid letter). You just need checks for out-of-bounds and valid two-character numbers, plus the memoization.

This makes a top-down approach pretty simple, although now I’m wondering how exactly you do a bottom-up approach. You only need to look two steps in the past at most, so if you do bottom-up you should be able to save memory. Probably one accumulator variable for the case where we are only doing one character and another accumulator for the case where we are doing two characters?

In the end, that turns out to be perfectly fine. I use a couple other library functions that make the constants in the time complexity a little higher, but asymptotically this is optimal. You can optimize by checking for '1' and '2' characters instead of calling stoi and checking bounds, although I think the latter is clearer to a reader.

The thing I don’t like about this solution is that the accumulator variables are “one off”; this necessitates the hacky length check at the beginning. Other solutions instead use current and prevByOne, so instead of int prevByOne = !(s[0] == '0'), prevByTwo = !(s[0] == '0');, you can do int current = !(s[0] == '0'), prevByOne = !(s[0] == '0'). The initial values are also a little weird to wrap your head around; I think practically speaking, what they mean is “are you allowed to start a string?”. If so (i.e. so long as you don’t start with a '0'), then there is 1 valid way to decode the first character, and that propagates forward in the DP…or something like that. There’s definitely gotta be a clearer way to illustrate this.

Quick and easy though.

int numDecodings(string s) {
    if (s.length() == 1) {
        return s[0] != '0';
    }

    int ways = 0;
    int prevByOne = !(s[0] == '0'), prevByTwo = !(s[0] == '0');
    for (int i = 1; i < s.length(); ++i) {
        ways = 0;
        if (s[i] != '0') {
            ways += prevByOne;
        }  
        int lastTwoLetters = stoi(s.substr(i - 1, 2));
        if (s[i - 1] != '0' && lastTwoLetters > 1 && lastTwoLetters <= 26) {
            ways += prevByTwo;
        }
        prevByTwo = prevByOne;
        prevByOne = ways; 
    }

    return ways;
}

With the adjusted accumulator variables:

int numDecodings(string s) {
    int current = !(s[0] == '0'), prevByOne = !(s[0] == '0');
    for (int i = 1; i < s.length(); ++i) {
        int ways = 0;
        if (s[i] != '0') {
            ways += current;
        }  
        int lastTwoLetters = stoi(s.substr(i - 1, 2));
        if (s[i - 1] != '0' && lastTwoLetters > 1 && lastTwoLetters <= 26) {
            ways += prevByOne;
        }
        prevByOne = current;
        current = ways; 
    }

    return current;
}