Decode Ways

Practice here Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

Intuition#

At position i, there are up to two ways to peel off the next decoded letter, and each depends only on the digits actually in front of you:

• Decode one digit s[i] as a letter — only valid if s[i] != '0' (no letter maps to "0"). Doing this leaves the rest of the string s[i+1..] to decode.
• Decode two digits s[i..i+1] as a letter — only valid if that two-digit number is between 10 and 26. Doing this leaves s[i+2..] to decode.

Since both choices are independent ways of making progress, the total ways from i is the sum of both (when valid):

ways(i) = ways(i+1)          [if s[i] != '0']
        + ways(i+2)          [if 10 <= s[i..i+1] <= 26]

with base case ways(n) = 1 — an empty suffix has exactly one way to decode it (do nothing). This is the same additive "sum of two smaller subproblems" shape as Climbing Stairs, except here we recurse forward from i to the end (i+1/i+2) instead of backward from n to 0, since validity of a choice depends on the digits ahead of i, not behind it. A '0' digit that isn't part of a valid two-digit pair (10 or 20) kills that branch entirely, which is why leading/standalone zeros drive the answer to 0.

The three implementations below solve this same recurrence with increasing efficiency:

• Recursion + Backtracking: direct top-down translation of ways(i); re-explores overlapping suffixes, giving exponential blowup.
• Tabulation: fills dp[i] bottom-up from i = n down to 0, so each suffix is computed once — O(n).
• Tabulation, space optimized: dp[i] only ever needs dp[i+1] and dp[i+2], so the array collapses to two rolling variables (next1, next2).

Brute Force: Recursion + Backtracking#

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

        int ways = dfs(s, i+1);
        if(i+1< s.size() && stoi(s.substr(i, 2))<=26)
            ways += dfs(s, i+2);
        return ways;
    }

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

Time Complexity: O(2ⁿ)

Space Complexity: O(n)

DP Solution: Tabulation#

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--)
        {
            if(s[i]!='0'){
                dp[i] = dp[i+1];
                if(i+1<n && stoi(s.substr(i, 2))<=26)
                    dp[i]+= dp[i+2];
            }
        }
        return dp[0];

    }
};

Time Complexity: O(n)

Space Complexity: O(n)

DP Solution: Tabulation - Space Optimized#

class Solution {
public:

    int numDecodings(string s) {
        int n = s.size();
        int next1 =1, next2=0;
        int curr=0;

        for(int i=n-1;i>=0;i--)
        {
            curr=0;
            if(s[i]!='0'){
                curr = next1;
                int two = (s[i] - '0') * 10 + (s[i + 1] - '0');
                if(i+1<n && two>=10 && two<=26)
                    curr+= next2;
            }
            next2 = next1;
            next1 = curr;
        }
        return curr;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)