Blind 75 - problem 20 : Decode Ways

 

Decode Ways – LeetCode Solution with Detailed Explanation

Problem Statement

You are given a string s containing only digits. Each digit (or pair of digits) can be mapped to a letter using the following mapping:

'A' -> 1, 'B' -> 2, ..., 'Z' -> 26

Your task is to determine how many different ways you can decode the given string.

Example 1:

Input:
s = "12"
Output:
2
Explanation:
The string "12" can be decoded in two ways:

• "AB" (1 → A, 2 → B)
• "L" (12 → L)

Example 2:

Input:
s = "226"
Output:
3
Explanation:
The string "226" can be decoded as:

• "BZ" (2 → B, 26 → Z)
• "VF" (22 → V, 6 → F)
• "BBF" (2 → B, 2 → B, 6 → F)

Example 3:

Input:
s = "06"
Output:
0
Explanation:
The string "06" cannot be decoded because numbers starting with '0' are invalid.

---

Optimal Approach – Dynamic Programming (DP)

Since we need to find the number of ways to decode a string efficiently, we use Dynamic Programming (DP). The key idea is to count the number of valid ways to decode the string up to each character while ensuring that invalid cases (like leading '0's) are handled properly.

Steps for Dynamic Programming Solution

1. Define dp[i] as the number of ways to decode the substring of s up to index i-1.
2. Base Cases:
   • dp[0] = 1 (An empty string has one way to decode)
   • dp[1] = 1 if s[0] is not '0', otherwise dp[1] = 0 (Invalid if first character is '0')
3. Recurrence Relation:
   • If s[i-1] ≠ '0', add dp[i-1] to dp[i] (single-digit decoding).
   • If s[i-2]s[i-1] forms a valid two-digit number (10 to 26), add dp[i-2] to dp[i].

---

LeetCode-Compatible C++ Code Implementation

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0; // Invalid case

        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1; // Single character decoding is valid unless '0'

        for (int i = 2; i <= n; i++) {
            // Single digit decoding (1 to 9)
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }

            // Two-digit decoding (10 to 26)
            int twoDigit = stoi(s.substr(i - 2, 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

---

Step-by-Step Explanation of Code

1. Edge Case Handling:
   • If the string is empty or starts with '0', return 0 (invalid input).
2. Initialize DP Array:
   • dp[0] = 1: Represents an empty string.
   • dp[1] = 1: Represents the first valid character (if it's not '0').
3. Loop through the String (i = 2 to n):
   • If s[i-1] is not '0', it can be decoded as a single character → dp[i] += dp[i-1].
   • If s[i-2]s[i-1] forms a number between 10 and 26, it can be decoded as a two-digit number → dp[i] += dp[i-2].
4. Return dp[n] as the final answer.

---

Dry Run / Execution Steps

Input: s = "226"

DP Array Calculation:

Index	s[i]	One-digit (dp[i-1])	Two-digit (dp[i-2])	dp[i]
0	""	1	-	1
1	"2"	1	-	1
2	"22"	1	2 → Valid	2
3	"226"	2	26 → Valid	3

Output: 3

---

Alternative Approaches & Why Not?

1. Brute Force – Recursion

• We try all possible ways of decoding the string by recursively considering single and double digits.
• Time Complexity: O(2^N) (Exponential, due to overlapping subproblems).
• Space Complexity: O(N) (Recursive stack).

2. Memoization (Top-Down DP)

• Uses recursion with memoization (unordered_map<int, int> memo) to store results of subproblems.
• Time Complexity: O(N)
• Space Complexity: O(N)

3. Space-Optimized DP (Iterative)

• Instead of maintaining the full dp[] array, use only two variables (prev1, prev2).
• Time Complexity: O(N)
• Space Complexity: O(1)

---

Best Solution & Why It’s Best

Approach	Time Complexity	Space Complexity	Optimal?
Brute Force Recursion	O(2^N)	O(N)	❌ No (Too slow)
Memoization (Top-Down DP)	O(N)	O(N)	✅ Yes
Bottom-Up DP (Tabulation)	O(N)	O(N)	✅ Yes
Space-Optimized DP	O(N)	O(1)	✅ Best

The space-optimized DP approach is the best since it runs in O(N) time while using only O(1) space.

---

Space-Optimized DP Implementation (Best Approach)

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;

        int prev1 = 1, prev2 = 1; // dp[i-1] and dp[i-2]

        for (int i = 1; i < s.size(); i++) {
            int current = 0;

            if (s[i] != '0') {
                current += prev1;
            }

            int twoDigit = stoi(s.substr(i - 1, 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                current += prev2;
            }

            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};

---

Conclusion

• We used DP to solve the problem efficiently.
• The best solution is the space-optimized DP approach (O(N) time, O(1) space).
• Similar problems to practice:
  • Climbing Stairs
  • House Robber
  • House Robber II

This ensures an optimized approach while keeping memory usage minimal! 🚀