LeetCode Solution 91 - Decode Ways

Problem Statement

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

• 'A' -> "1"
• 'B' -> "2"
• ...
• 'Z' -> "26"

Given a non-empty string s containing digits, determine the total number of ways to decode it.

Constraints:

• 1 <= s.length <= 100
• s contains only digits and does not contain leading zeros except for "0" itself.

Optimal Approach - Dynamic Programming (Bottom-Up)

The most efficient way to solve this problem is Dynamic Programming (DP).

Explanation:

1. If s[i] is '0', it must be part of a valid two-digit number (i.e., "10" to "26").
2. If s[i-1]s[i] forms a number between "10" and "26", it can be treated as a single character.
3. Use a dp array where dp[i] represents the number of ways to decode the substring s[0...i-1].

Transition Formula:

• If s[i-1] != '0', dp[i] += dp[i-1] (single digit decode)
• If s[i-2]s[i-1] is between "10" and "26", dp[i] += dp[i-2] (two-digit decode)

C++ Code (LeetCode-Compatible)

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = s[0] != '0' ? 1 : 0;
        
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            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

1. Edge Case: If s starts with '0', return 0.
2. Initialize dp array:
   • dp[0] = 1 (Base case: empty string has one way to decode)
   • dp[1] = 1 if s[0] != '0' else 0.
3. Loop through the string:
   • If s[i-1] is not '0', add dp[i-1].
   • If the last two digits form a number between "10" and "26", add dp[i-2].
4. Return dp[n] as the total ways.

Dry Run / Execution Steps

Example:

Input: s = "226"

DP Array Updates:

i	s[i-1]	dp[i] Calculation	dp[i] Value
0	-	dp[0] = 1 (base case)	1
1	'2'	dp[1] = 1 (single valid digit)	1
2	'2'	dp[2] = dp[1] + dp[0] (valid "22")	2
3	'6'	dp[3] = dp[2] + dp[1] (valid "26")	3

Output: 3

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	Exponential $O(2^n)$	O(n)	Too slow for large inputs
Memoization (Top-Down DP)	O(n)	O(n)	Extra space usage
Bottom-Up DP (Best)	O(n)	O(n)	Optimized for both time and space

Best Solution & Why It’s Best

The Bottom-Up DP approach is the most efficient because:

1. It avoids recursion overhead.
2. It ensures optimal decoding paths without unnecessary computations.
3. It runs in O(n) time complexity with O(n) space complexity.

Complexity Analysis

• Time Complexity: O(n), iterating through the string once.
• Space Complexity: O(n), storing results in a dp array.

Conclusion

• The best approach is Bottom-Up Dynamic Programming.
• Other methods like recursion or memoization use unnecessary extra space or time.
• Recommended practice problems:
  • Climbing Stairs (LeetCode 70)
  • House Robber (LeetCode 198)
  • Decode Ways II (LeetCode 639)