Neetcode - Decode Ways

Write code today that your future self will thank you for.

This problem can be quite tricky if you're not familiar with this kind of real-world character-to-number mapping. It requires a combination of recursive thinking, dynamic programming, string parsing, edge case handling, and even elements of backtracking. In short, it touches on several core concepts that are essential in programming interviews.

Below are a series of solutions, progressing from the most basic to the more optimized:

class SolutionRecursive {
public:
    int dfs(int i, string& s) {
        int ch = s[i];
        int size = s.size();
        
        if (ch == '0') return 0;
        if (i == size) return 1;

        int cnt = dfs(i + 1, s);
        if (i < size - 1) {
            if (ch == '1' ||
                (ch == '2' && s[i + 1] < '7')) {
                    cnt += dfs(i + 2, s);
            }
        }

        return cnt;
    }

    int numDecodings(string s) {
        return dfs(0, s);   
    }
};

In this case, we start from index 0 and first check if the character at that position is '0' or if we've reached the end of the string. If these edge cases are cleared, we then recursively process the next index.

At each position, we consider one or two characters ahead to see if a valid 1-digit or 2-digit mapping can be formed. That’s essentially the core idea.

To add memoization, we simply introduce a memo table to store and reuse results for each index.

class SolutionRecursiveMemo {
    unordered_map<int, int> memo;
public:
    int dfs(int i, string& s) {
        int ch = s[i];
        int size = s.size();

        if (ch == '0') return 0;
        if (i == size) return 1;
        if (memo.count(i)) return memo[i];

        int cnt = dfs(i + 1, s);
        if (i < size - 1) {
            int ch_num = stoi(s.substr(i, 2));
            if (ch_num <= 26) {
                cnt += dfs(i + 2, s);
            }
        }

        return memo[i] = cnt;
    }

    int numDecodings(string s) {
        return dfs(0, s);   
    }
};

Let’s also try the bottom-up approach. But wait… what exactly is bottom-up?
Well, here’s the idea:

Bottom-Up

1. Build the solution starting from the smallest subproblems, typically from the end toward the beginning.
2. Avoids recursion entirely by using iteration and filling up a DP table.
3. Efficient in both time and space, especially when optimized with techniques like space reduction.

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);

        dp[n] = 1;
        for (int i = n - 1; i >= 0; --i) {
            char ch = s[i];
            if (ch == '0') dp[i] = 0;
            else {
                dp[i] = dp[i + 1];

                if (i + 1 < n) {
                    int ch_num = stoi(s.substr(i, 2));
                    if (ch_num <= 26) {
                        dp[i] += dp[i + 2];
                    }
                }
            }
        }

        return dp[0];
    }
};

You can see that this approach starts from the end of the array. But honestly, it doesn’t feel all that different to me—since even the earlier methods also rely on results from future (or forward) steps and gradually build backward to form the final answer. After all, that’s a key characteristic of dynamic programming problems, isn’t it?

Conclusion

A brief note on DP.

It’s completely normal to feel anxious when encountering a DP problem during an interview. But take a deep breath and give yourself time. Nobody is perfect, and it’s okay to refer to solutions while practicing. What matters is that you keep working on it, even if it feels confusing at first. Staying stuck and nervous doesn’t help—be patient with yourself, and improvement will come with practice.