🔢 Decode Ways - The Discovery Journey

The Problem (Quick Glance)

LC 91: Decode Ways

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).

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

Example 1: "12" can be decoded as:

• "AB" with grouping (1 2)
• "L" with grouping (12) → Answer: 2 ways

Example 2: "226" can be decoded as:

• "BZ" with grouping (2 26)
• "VF" with grouping (22 6)
• "BBF" with grouping (2 2 6) → Answer: 3 ways

Example 3: "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6) → Note: (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" ≠ "06"

Initial Observations:

• This is a counting problem - count the number of ways, not find all decodings
• At each position: decision to take 1 digit or 2 digits
• Valid single digits: 1-9 (not 0)
• Valid two digits: 10-26 (not 01-09, not 27+)

Let's start solving!

---

1. My First Approach: Thinking Recursively

My thought process:

"When I see 'count the number of ways,' I think: this is a decision tree problem.

At each position, I can:

• Take 1 digit (if valid)
• Take 2 digits (if valid)

This smells like recursion!"

Solution 1: Unoptimized Recursive (Brute Force)

class Solution {
    public int numDecodings(String s) {
        return decode(s, 0);
    }

    private int decode(String s, int index) {
        // Base case: successfully decoded entire string
        if (index == s.length()) {
            return 1;
        }

        // Base case: hit a leading zero (invalid)
        if (s.charAt(index) == '0') {
            return 0;
        }

        // Choice 1: Take 1 digit
        int ways = decode(s, index + 1);

        // Choice 2: Take 2 digits (if valid)
        if (index + 1 < s.length()) {
            // Extract two-digit number
            int twoDigit = (s.charAt(index) - '0') * 10 + (s.charAt(index + 1) - '0');
            if (10 <= twoDigit && twoDigit <= 26) {
                ways += decode(s, index + 2);
            }
        }

        return ways;
    }
}

Complexity Analysis:

• Time: O(2^n) - Exponential! 😱 Each position branches into 2 recursive calls
• Space: O(n) - Recursion call stack depth

Why This Is Slow:

decode("226", 0)
├── decode("226", 1)
│   ├── decode("226", 2)  ← Calculated here
│   │   ├── decode("226", 3) → 1
│   │   └── ...
│   └── decode("226", 3) → 1
└── decode("226", 2)      ← Calculated AGAIN here!
    └── decode("226", 3) → 1

The Problem

I'm recalculating the same subproblems over and over!

decode(2) gets computed multiple times. For s = "1111111111" (10 ones):

• Pure recursion: ≈89 function calls (Fibonacci-like growth)
• This is horribly inefficient!

My realization: "Wait, I'm doing the same work repeatedly. Can I remember what I've already computed?"

Execution Trace for "12":

decode(0): Looking at '1'
├─ Choice 1: Take '1' → decode(1)
│              Looking at '2'
│              ├─ Choice 1: Take '2' → decode(2)
│              │              Base case: index==length → return 1
│              │  Returns: 1
│              └─ Choice 2: Can't take 2 (out of bounds)
│              Returns: 1
│  Got: 1
└─ Choice 2: Take '12' → decode(2)
               Base case: index==length → return 1
   Got: 1

Total: 1 + 1 = 2 ✓

---

2. Optimization Round 1: Adding Memoization (Top-Down DP)

My thought: "Let me cache the results so I don't recalculate them!"

Solution 2: Top-Down DP with Memoization

class Solution {
    public int numDecodings(String s) {
        // Memo array: memo[i] = number of ways to decode from index i
        // Use Integer[] so we can distinguish "not computed" (null) from "computed as 0"
        Integer[] memo = new Integer[s.length()];
        return decode(s, 0, memo);
    }

    private int decode(String s, int index, Integer[] memo) {
        // Base case: successfully decoded entire string
        if (index == s.length()) {
            return 1;
        }

        // Base case: hit a leading zero (invalid)
        if (s.charAt(index) == '0') {
            return 0;
        }

        // ✨ MEMOIZATION CHECK: Have we solved this subproblem before?
        if (memo[index] != null) {
            return memo[index];  // Cache hit! 🚀
        }

        // Choice 1: Take 1 digit
        int ways = decode(s, index + 1, memo);

        // Choice 2: Take 2 digits (if valid)
        if (index + 1 < s.length()) {
            int twoDigit = (s.charAt(index) - '0') * 10 + (s.charAt(index + 1) - '0');
            if (10 <= twoDigit && twoDigit <= 26) {
                ways += decode(s, index + 2, memo);
            }
        }

        // ✨ CACHE THE RESULT before returning
        memo[index] = ways;
        return ways;
    }
}

Complexity Analysis:

• Time: O(n) - Each subproblem computed once! ✨
• Space: O(n) memo array + O(n) call stack = O(n) total

What Changed?

Only 3 lines added to the pure recursive solution!

1. Create memo array
2. Check cache before computing
3. Store result in cache before returning

That's the beauty of memoization - minimal code change, massive performance gain!

Why This Is Fast:

decode(0, memo) [memo = [null, null, null]]
├─ decode(1, memo)
│  ├─ decode(2, memo) → computed and cached: memo[2] = 1
│  └─ decode(3) → 1
│  Result: memo[1] = 2
└─ decode(2, memo) → Cache hit! Returns memo[2] = 1 immediately 🚀

Total: 2 + 1 = 3
Final memo: [3, 2, 1]

The Improvement

Each subproblem is computed exactly once and reused from cache.

Time complexity drops from O(2^n) to O(n)! 🎉

My next thought: "This is much better! But I'm still using recursion with a call stack. Can I eliminate that?"

---

3. Optimization Round 2: Going Iterative (Bottom-Up DP)

My thought: "Instead of recursing from top down, what if I build the solution from bottom up?"

Solution 3: Bottom-Up DP with Tabulation

class Solution {
    public int numDecodings(String s) {
        int n = s.length();

        // dp[i] = number of ways to decode substring from index i to end
        int[] dp = new int[n + 1];

        // BASE CASE: Empty string (reached the end)
        dp[n] = 1;  // One way to decode an empty string: do nothing

        // BUILD FROM RIGHT TO LEFT (from end towards beginning)
        for (int i = n - 1; i >= 0; i--) {
            // INVALID CASE: Current digit is '0'
            if (s.charAt(i) == '0') {
                dp[i] = 0;
                continue;
            }

            // CHOICE 1: Take single digit
            dp[i] = dp[i + 1];

            // CHOICE 2: Take two digits (if valid)
            if (i + 1 < n) {
                int twoDigit = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
                if (10 <= twoDigit && twoDigit <= 26) {
                    dp[i] += dp[i + 2];
                }
            }
        }

        // Answer: number of ways to decode from index 0
        return dp[0];
    }
}

Complexity Analysis:

• Time: O(n) - Single loop through all positions
• Space: O(n) - DP array only (no recursion stack!)

Why Bottom-Up?

1. ✅ No recursion overhead - Simple loop instead of function calls
2. ✅ No stack overflow risk - Works for very large n
3. ✅ Better cache locality - Sequential memory access
4. ✅ Easier to optimize further - Can reduce to O(1) space

Execution Trace for "226":

Initial: dp = [0, 0, 0, 1]
               i=0 i=1 i=2 i=3

i=2: s[2]='6' (not '0')
     dp[2] = dp[3] = 1
     Can't take 2 digits (out of bounds)
     dp = [0, 0, 1, 1]

i=1: s[1]='2' (not '0')
     dp[1] = dp[2] = 1
     Take "26": valid (10≤26≤26)
     dp[1] += dp[3] = 1 + 1 = 2
     dp = [0, 2, 1, 1]

i=0: s[0]='2' (not '0')
     dp[0] = dp[1] = 2
     Take "22": valid (10≤22≤26)
     dp[0] += dp[2] = 2 + 1 = 3
     dp = [3, 2, 1, 1]

Return: dp[0] = 3 ✓

Reading the DP Array

dp = [3, 2, 1, 1] tells us:

• dp[0]=3: 3 ways to decode from index 0 to end
• dp[1]=2: 2 ways to decode from index 1 to end
• dp[2]=1: 1 way to decode from index 2 to end
• dp[3]=1: 1 way to decode empty string (base case)

My observation: "Wait, I only ever need the last 2 values. Do I really need the entire array?"

---

4. Final Optimization: Space Optimization (O(1) Space)

My thought: "Since I only look back 2 positions, I can just track 2 variables!"

Solution 4: Space-Optimized Bottom-Up

class Solution {
    public int numDecodings(String s) {
        int n = s.length();

        // Instead of dp array, use just 2 variables
        // prev2 = dp[i+2] (two positions ahead)
        // prev1 = dp[i+1] (one position ahead)

        int prev2 = 1;  // dp[n] = 1 (base case)
        int prev1 = s.charAt(n - 1) == '0' ? 0 : 1;  // dp[n-1]

        // BUILD FROM RIGHT TO LEFT (start at n-2)
        for (int i = n - 2; i >= 0; i--) {
            int current;

            // INVALID CASE: Current digit is '0'
            if (s.charAt(i) == '0') {
                current = 0;
            } else {
                // CHOICE 1: Take single digit
                current = prev1;

                // CHOICE 2: Take two digits (if valid)
                if (i + 1 < n) {
                    int twoDigit = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
                    if (10 <= twoDigit && twoDigit <= 26) {
                        current += prev2;
                    }
                }
            }

            // SLIDE THE WINDOW: shift values for next iteration
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;  // This holds the answer for index 0
    }
}

Complexity Analysis:

• Time: O(n) - Same as before
• Space: O(1) - Only 3 variables! 🎯

Execution Trace for "226":

Initialization:
  prev2 = 1  (dp[3])
  prev1 = 1  (dp[2], since '6' ≠ '0')

i=1: s[1]='2'
     current = prev1 = 1
     "26" valid → current += prev2 = 1 + 1 = 2
     Shift: prev2=1, prev1=2

i=0: s[0]='2'
     current = prev1 = 2
     "22" valid → current += prev2 = 2 + 1 = 3
     Shift: prev2=2, prev1=3

Return: prev1 = 3 ✓

The Variable Dance

Before iteration i:

prev2 = dp[i+2]
prev1 = dp[i+1]

During iteration i:

current = dp[i]  (compute using prev1 and prev2)

After iteration i (prepare for i-1):

prev2 = prev1  (shift right)
prev1 = current  (shift right)

This "sliding window" technique is common in DP space optimization!

---

5. Solution Evolution Summary

Approach	Time	Space	Recursion?	Key Insight
1. Unoptimized Recursive	O(2^n)	O(n) stack	Yes	Establishes recurrence relation
2. Top-Down (Memoization)	O(n)	O(n) + O(n) stack	Yes	Cache eliminates redundant work
3. Bottom-Up (Tabulation)	O(n)	O(n) array	No	Build iteratively, no recursion
4. Space-Optimized	O(n)	O(1)	No	Only need last 2 values

The Learning Journey:

1. 🤔 Start with natural recursive thinking
2. 💡 Realize we're repeating work → add memoization
3. ⚡ Eliminate recursion overhead → go bottom-up
4. 🎯 Recognize we only need 2 values → space optimize

---

6. Deep Dive: Understanding Why This Works

Now that we've built the solution, let's understand the deeper concepts.

6.1 The Index Parameter & View Window Concept

What IS the index Parameter?

The Core Concept

index is a pointer that says: "Start decoding from THIS position onwards"

It's NOT creating substrings. It's NOT copying anything. It's just saying:

• "Hey future recursive call, YOU handle everything from position index to the end"
• "I don't care what you do—just tell me HOW MANY ways you found"

Visual - Same String, Different Starting Points:

┌───┬───┬───┐
│ 1 │ 2 │ 6 │
└───┴───┴───┘
  ↑
decode(s, 0): "I see everything from here to the end"

┌───┬───┬───┐
│ 1 │ 2 │ 6 │
└───┴───┴───┘
      ↑
decode(s, 1): "I see everything from HERE to the end"

┌───┬───┬───┐
│ 1 │ 2 │ 6 │
└───┴───┴───┘
          ↑
decode(s, 2): "I see everything from HERE to the end"

Critical Understanding

We're NOT creating substrings! We're just moving our "reading head" forward.

Benefits:

1. Memory: Only ONE string exists in memory
2. Time: Passing an integer is O(1)
3. Efficiency: No unnecessary copying

6.2 Edge Cases & Valid Two-Digit Numbers

The "06" Problem

Common Mistake

You might think valid two-digit numbers are 1-26, but they're actually 10-26!

Why?

For "06":

• Character arithmetic: ('0' - '0') * 10 + ('6' - '0') = 0 * 10 + 6 = 6
• Integer.parseInt("06") = 6

Both give 6, but "06" is NOT a valid encoding!

The Key Insight

"06" as a two-digit decode is ALSO invalid!

Why?

• No letter maps to "06"
• Only "6" maps to 'F', and "6" ≠ "06" (as the problem states)

The Fix: Check 10-26, Not 0-26

if (index + 1 < s.length()) {
    int twoDigit = (s.charAt(index) - '0') * 10 + (s.charAt(index + 1) - '0');
    if (10 <= twoDigit && twoDigit <= 26) {  // ✓ Fixed range!
        ways += decode(s, index + 2);
    }
}

Valid Two-Digit Encodings

• "01" through "09" are invalid (leading zeros)
• "10" through "26" are valid ('J' through 'Z')
• "27"+ are invalid (no such letters)

6.3 Common Edge Cases

Edge Case 1: s = "10"

// At index 0: s[0]='1'
// Choice 1: Take '1' → recurse on index 1 → hits '0' → returns 0
// Choice 2: Take '10' → twoDigit = 10 (valid) → recurse on index 2 → returns 1
// Total: 0 + 1 = 1 ✓

Edge Case 2: s = "206"

// index=0: s[0]='2'
//   Take '2': decode(1) → s[1]='0' → return 0
//   Take '20': twoDigit=20 (valid) → decode(2)
//     index=2: s[2]='6'
//       Take '6': decode(3) → return 1
//   Total: 0 + 1 = 1 ✓

Without the 10 <= check, we'd incorrectly allow "06"!

---

7. Mastery & Key Takeaways

7.1 Framework & Pattern Recognition

When You See "Count the Number of Ways"

1. Identify the decision points: What choices do I have at each step?
2. Define the state: What information do I need to make those choices?
3. Find the recurrence: How do smaller subproblems combine?
4. Establish base cases: When do I stop recursing?

This same framework applies to:

• Climbing stairs (1 or 2 steps)
• Coin change (which coin to take)
• Path counting in grids (go right or down)

7.2 Key Takeaways

1. ✅ Start with recursion: Natural way to think about the problem
2. ✅ Optimize with memoization: Eliminate redundant computation (O(2^n) → O(n))
3. ✅ Convert to bottom-up: Remove recursion overhead
4. ✅ Space optimize: Only keep what you need (O(n) → O(1))
5. ✅ State Definition: decode(index) = number of ways to decode from index onwards
6. ✅ Valid ranges: Single digits 1-9, two digits 10-26
7. ✅ Index as cursor: Pass same string, different starting position
8. ✅ Boundary checks: Prevent array out of bounds errors

The Learning Journey: Start simple, optimize iteratively, understand deeply.

7.3 Strategy Selection

Use Top-Down when:

• ✅ The recursive solution is very natural and clear
• ✅ Not all subproblems need to be solved
• ✅ You're prototyping or in an interview (fastest to code)

Use Bottom-Up when:

• ✅ You need to avoid recursion stack
• ✅ All subproblems must be computed anyway
• ✅ You want guaranteed O(n) space without stack overhead

Use Space-Optimized when:

• ✅ Memory is constrained
• ✅ You've confirmed the pattern (only need last k values)
• ✅ You're optimizing a working solution

Interview Strategy

1. Start with recursion - Show you understand the problem structure
2. Add memoization - Demonstrate you know about overlapping subproblems
3. Convert to bottom-up - Show you can eliminate recursion
4. Optimize space - Prove you can identify optimization opportunities

Each step shows deeper understanding! 🎓

The Evolution Path:

Pure Recursion (O(2^n) time, O(n) space)
    ↓ "Same subproblems computed multiple times"
Top-Down with Memo (O(n) time, O(n) space)
    ↓ "Still using recursion - can we eliminate the stack?"
Bottom-Up DP (O(n) time, O(n) space)
    ↓ "Do we really need the entire array?"
Space-Optimized (O(n) time, O(1) space) ✨

You've Mastered the Journey!

From exponential recursion to optimal O(n) time, O(1) space solution.

This progression applies to hundreds of DP problems. You now have the complete toolkit! 🎯