Decode Ways - The Recursive Discovery Journey

The Problem

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: "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" is different from "06".

---

Layer 1: Designer's Brain - The Discovery Journey

First Instinct: What's the actual question?

When I see "count the number of ways," my brain immediately thinks:

This is a counting problem, not a finding problem.

I don't need to return all the decodings—just how many exist.

Second Thought: What makes one path different from another?

Let me trace through "226":

1. If I take '2' first → I have "26" left
2. If I take '22' first → I have "6" left
3. If I take '2' first (again) → but then '2' next → I have "6" left

Key Insight: Decision Tree

At each position, I'm making a DECISION:

• Take 1 digit, or
• Take 2 digits

This smells like a decision tree → recursion territory.

Third Thought: What's the base case?

Let me walk to the end:

• If I've consumed the entire string → that's 1 valid way
• If I hit an invalid state (like "06") → that's 0 ways

The Critical Insight (PREREQUISITE #1)

The Optimal Substructure

The problem has optimal substructure: If I know how many ways to decode the remaining substring, I can build up the answer.

Example: For "226"

• If I take '2', the answer = (ways to decode "26")
• If I take '22', the answer = (ways to decode "6")
• Total = sum of both

The "messy discovery": I don't need to track WHAT the decodings are, just COUNT them!

---

Layer 2: The Thought Process Chronologically

Step 1: What information do I need to track?

Just my current position in the string. That's my state!

decode(s, index) = number of ways to decode s[index:]

Step 2: What are my choices at each position?

Choice 1: Take 1 digit

• Valid if: s.charAt(index) is not '0' (because 'A'-'Z' map to "1"-"26")
• Recurse on: decode(s, index + 1)

Choice 2: Take 2 digits

• Valid if:
  • I have at least 2 digits left AND
  • The two-digit number is between 10-26
• Recurse on: decode(s, index + 2)

Step 3: When do I stop?

Base case 1: index == s.length() → I've decoded everything → return 1

Base case 2: s.charAt(index) == '0' → Invalid! Can't decode starting with 0 → return 0

---

Layer 3: Coder's Brain - Why This Implementation?

Why recursion?

Because each decision point naturally branches into smaller subproblems. The recursion tree explores all valid paths.

Why start from index 0?

We process left-to-right, making decisions sequentially—just like how you'd actually decode by hand.

Why return integers?

We're counting paths, not collecting them. Each recursive call returns a count that we sum up.

Why a helper method?

Java Design Pattern

The main method signature is fixed (takes only String s), but our recursive function needs to track the index.

So we create a helper method that does the actual work.

---

Layer 4: The Unoptimized Solution

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;
    }
}

With Debug Output (Visualize Execution)

This version uses explicit variable names and adds logging to show execution flow:

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

    private int decode(String s, int index) {
        // Base case: reached the end
        if (index == s.length()) {
            System.out.println("✓ Reached end! Returning 1");
            return 1;  // ← THIS IS WHERE WE COUNT A PATH
        }

        // Base case: leading zero
        if (s.charAt(index) == '0') {
            System.out.println("✗ Leading zero! Returning 0");
            return 0;  // ← THIS PATH IS INVALID
        }

        System.out.println("At index " + index + ", char: " + s.charAt(index));

        // Choice 1: Take 1 digit
        System.out.println("  Exploring: take 1 digit");
        int waysFromChoice1 = decode(s, index + 1);
        System.out.println("  Choice 1 returned: " + waysFromChoice1);

        int waysFromChoice2 = 0;

        // 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) {
                System.out.println("  Exploring: take 2 digits (" + twoDigit + ")");
                waysFromChoice2 = decode(s, index + 2);
                System.out.println("  Choice 2 returned: " + waysFromChoice2);
            }
        }

        int totalWays = waysFromChoice1 + waysFromChoice2;
        System.out.println("At index " + index + ": combining " + waysFromChoice1 + " + " + waysFromChoice2 + " = " + totalWays);

        return totalWays;
    }
}

Example Output for s = "12":

At index 0, char: 1
  Exploring: take 1 digit
At index 1, char: 2
  Exploring: take 1 digit
✓ Reached end! Returning 1
  Choice 1 returned: 1
At index 1: combining 1 + 0 = 1
  Choice 1 returned: 1
  Exploring: take 2 digits (12)
✓ Reached end! Returning 1
  Choice 2 returned: 1
At index 0: combining 1 + 1 = 2

Without Debug Logs (Clean Version)

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

    private int decode(String s, int index) {
        // Base case: reached the end
        if (index == s.length()) {
            return 1;
        }

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

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

        int waysFromChoice2 = 0;

        // 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) {
                waysFromChoice2 = decode(s, index + 2);
            }
        }

        int totalWays = waysFromChoice1 + waysFromChoice2;

        return totalWays;
    }
}

Alternative Approach (Explicit Variable Names)

This version uses more explicit variable names for clarity:

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

    private int decode(String s, int index) {
        // Base case: reached the end
        if (index == s.length()) {
            return 1;
        }

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

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

        int waysFromChoice2 = 0;

        // 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) {
                waysFromChoice2 = decode(s, index + 2);
            }
        }

        int totalWays = waysFromChoice1 + waysFromChoice2;

        return totalWays;
    }
}

---

Layer 5: Java-Specific Design Decisions

Why s.charAt(index) instead of s[index]?

Java Strings

Strings in Java are objects, not primitive arrays. We use the charAt() method to access individual characters.

Why (s.charAt(index) - '0')?

This is character arithmetic:

// s.charAt(index) returns a char like '2'
// '2' has ASCII value 50
// '0' has ASCII value 48
// '2' - '0' = 50 - 48 = 2 (the integer!)

To convert two consecutive digits to a number:

// First digit:  (s.charAt(index) - '0') * 10
// Second digit: (s.charAt(index + 1) - '0')
// Combined:     27 for the string "27"

Why a separate private helper method?

Encapsulation: The recursive logic is an implementation detail. The outside world only needs to know numDecodings(String s). The decode(String s, int index) helper is internal.

---

Layer 6: Edge Cases as Concept Validators

Edge Case 1: s = "0"

// Start at index 0
// s.charAt(0) == '0' → return 0

Why it works

My base case catches invalid leading zeros immediately.

---

Edge Case 2: s = "10"

// At index 0: s.charAt(0) = '1'

// Choice 1: Take '1' → recurse on index 1 → hits '0' → returns 0
// Choice 2: Take '10' → twoDigit = 1*10 + 0 = 10
//                     → 10 ≤ 26 ✓ → recurse on index 2 → returns 1

// Total: 0 + 1 = 1

Why it works

Even though '1' alone is valid, the remaining string is invalid, so that path contributes 0.

---

Edge Case 3: s = "27"

// At index 0: s.charAt(0) = '2'

// Choice 1: Take '2' → decode(s, 1) → eventually returns 1
// Choice 2: Take '27' → twoDigit = 2*10 + 7 = 27
//                     → 27 > 26 → skip this choice

// Total: 1

Why it works

My two-digit validation prevents invalid mappings.

---

Edge Case 4: s = "12"

// At index 0:
// Choice 1: Take '1' → decode(s, 1) → decode "2" → 1
// Choice 2: Take '12' → twoDigit = 12 ≤ 26 → decode(s, 2) → returns 1

// Total: 2 ✓

---

Edge Case 5: s = "226" (Full Tree Trace)

decode(s, 0): s[0]='2'
├─ Take '2': decode(s, 1)
│  └─ s[1]='2'
│     ├─ Take '2': decode(s, 2)
│     │  └─ s[2]='6'
│     │     └─ Take '6': decode(s, 3) → index==length → return 1
│     └─ Take '26': decode(s, 3) → index==length → return 1
│  Result: 1 + 1 = 2
│
└─ Take '22': decode(s, 2)
   └─ s[2]='6'
      └─ Take '6': decode(s, 3) → index==length → return 1
   Result: 1

Total: 2 + 1 = 3 ✓

---

Layer 7: The Critical Insight About 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?

Let's test both approaches for extracting the two-digit number:

Method 1: Character Arithmetic

int twoDigit = (s.charAt(index) - '0') * 10 + (s.charAt(index + 1) - '0');

Method 2: Integer.parseInt

int twoDigit = Integer.parseInt(s.substring(index, index + 2));

For "06":

• Method 1: ('0' - '0') * 10 + ('6' - '0') = 0 * 10 + 6 = 6
• Method 2: Integer.parseInt("06") = 6

They give the SAME result!

So What's the Problem?

Let's trace through s = "206":

// At index 1, we're looking at '0':

// Choice 1: Take '0' alone → Invalid! Leading zero → return 0
// Choice 2: Take '06' together → What should happen?

The Key Insight

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

Why? Because:

• If we can decode '06', that means we're treating position 1-2 as a SINGLE unit
• But '06' is not a valid encoding—no letter maps to "06"
• Only "6" maps to 'F', and "6" ≠ "06" (as the problem states)

The Bug Without Proper Range Check

if (index + 1 < s.length()) {
    int twoDigit = Integer.parseInt(s.substring(index, index + 2));
    if (twoDigit <= 26) {  // ❌ 6 <= 26 ✓ → We'd INCORRECTLY allow "06"!
        ways += decode(s, index + 2);
    }
}

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)

Edge Case Validator: Does the Fix Work?

Test: s = "206"

// index=0: s[0]='2'
//   Take '2': decode(1)
//     index=1: s[1]='0' → return 0 (leading zero!)
//   Take '20': twoDigit=20, 10≤20≤26 ✓ → decode(2)
//     index=2: s[2]='6'
//       Take '6': decode(3) → return 1
//     Result: 1
// Total: 0 + 1 = 1 ✓

Without the 10 <= check, we'd get the wrong answer!

---

Layer 8: Understanding the index Parameter

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"

Step-by-Step Trace: s = "12"

Call 1: decode(s, 0)

String s = "12"
            ↑
         index=0

I'm at position 0, looking at '1'.

My job: Decide what to do with '1', then let someone else handle the rest.

My choices:

1. Take '1' alone → "Someone else, handle everything from position 1 onwards!"
2. Take '12' together → "Someone else, handle everything from position 2 onwards!"

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

What does decode(s, 1) mean?

• Same string "12"
• But now, start processing from index 1
• "You handle s[1:], which is the character '2' onwards"

---

Call 2: decode(s, 1) (spawned by Choice 1)

String s = "12"
             ↑
          index=1

I'm at position 1, looking at '2'.

My choices:

1. Take '2' alone → "Someone else, handle everything from position 2 onwards!"
2. Take '2?' together → Can't! There's no index 2, so skip this choice.

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

---

Call 3: decode(s, 2) (spawned by Choice 1 of Call 2)

String s = "12"
               ↑
            index=2

I'm at position 2, which is PAST the end of the string!

if (index == s.length()) {  // 2 == 2 ✓
    return 1;  // Success! We decoded everything!
}

This returns 1 back to Call 2.

---

Back to Call 2: decode(s, 1)

int ways = decode(s, index + 1);  // Got back 1

So ways = 1.

Now check Choice 2:

if (index + 1 < s.length()) {  // 1 + 1 < 2? → 2 < 2? NO!
    // Skip this choice
}

Return ways = 1 back to Call 1.

---

Back to Call 1: decode(s, 0)

int ways = decode(s, index + 1);  // Got back 1 from decode(s, 1)

So ways = 1 so far.

Now check Choice 2:

if (index + 1 < s.length()) {  // 0 + 1 < 2? → 1 < 2? YES!
    int twoDigit = (s.charAt(0) - '0') * 10 + (s.charAt(1) - '0');
    // twoDigit = 1*10 + 2 = 12

    if (10 <= twoDigit && twoDigit <= 26) {  // 10 <= 12 <= 26? YES!
        ways += decode(s, index + 2);  // decode(s, 2)
    }
}

---

Call 4: decode(s, 2) (spawned by Choice 2 of Call 1)

String s = "12"
               ↑
            index=2

Same as Call 3!

if (index == s.length()) {  // 2 == 2 ✓
    return 1;
}

Returns 1 back to Call 1.

---

Back to Call 1 (final calculation)

int ways = 1;  // From decode(s, 1)
ways += 1;     // From decode(s, 2)
// ways = 2

return 2;  // Final answer!

---

Layer 9: The Key Insight - Index is a "View Window"

Think of the string as a physical tape:

┌───┬───┬───┬───┐
│ 1 │ 2 │ 2 │ 6 │
└───┴───┴───┴───┘
  ↑
index=0: "I see everything from here to the end"

When I call decode(s, 1):

┌───┬───┬───┬───┐
│ 1 │ 2 │ 2 │ 6 │
└───┴───┴───┴───┘
      ↑
index=1: "I see everything from HERE to the end"

When I call decode(s, 2):

┌───┬───┬───┬───┐
│ 1 │ 2 │ 2 │ 6 │
└───┴───┴───┴───┘
          ↑
index=2: "I see everything from HERE to the end"

Critical Understanding

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

---

Layer 10: Why This Design?

Alternative (less efficient): Actually create substrings

private int decode(String s) {
    if (s.isEmpty()) {
        return 1;
    }

    if (s.charAt(0) == '0') {
        return 0;
    }

    // Choice 1: Take 1 digit
    int ways = decode(s.substring(1));  // ❌ Create new string!

    // Choice 2: Take 2 digits
    if (s.length() >= 2) {
        int twoDigit = Integer.parseInt(s.substring(0, 2));
        if (10 <= twoDigit && twoDigit <= 26) {
            ways += decode(s.substring(2));  // ❌ Create another new string!
        }
    }

    return ways;
}

Problems with Substring Approach

1. Memory: Each recursive call creates a NEW string object
2. Time: Copying characters takes O(n) time per call
3. Waste: We never modify the original string—why copy it?

Our approach: Pass index as a "cursor"

private int decode(String s, int index) {
    // Just move the cursor, no copying!
}

Benefits

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

---

Layer 11: Visual - The Call Tree for "12"

decode(s="12", index=0)
│
├─ Choice 1: Take '1' → decode(s="12", index=1)
│                       │
│                       └─ Choice 1: Take '2' → decode(s="12", index=2)
│                                                └─ Base case: return 1
│                       Return: 1
│
└─ Choice 2: Take "12" → decode(s="12", index=2)
                         └─ Base case: return 1

Total: 1 + 1 = 2

Notice

Same string "12" is passed to every call! Only index changes.

---

Layer 12: The Conceptual Model

Think of it like reading a book with bookmarks:

String s = "The quick brown fox"
            ↑
         index=0: Start reading from 'T'

decode(s, 4):
String s = "The quick brown fox"
                ↑
         index=4: Start reading from 'q'

decode(s, 10):
String s = "The quick brown fox"
                      ↑
         index=10: Start reading from 'b'

You're not tearing pages out of the book! You're just moving your bookmark.

---

Layer 13: The "Weirdness" Explained

int ways = decode(s, index + 1);

What Feels Weird

"Where does the substring happen?"

The Revelation

It DOESN'T! There's no substring.

• index tells the function: "Start your work from THIS position"
• The function looks at s.charAt(index) and s.charAt(index + 1)
• It never needs to see the characters BEFORE index—those are already processed!

Mental Model Shift

Old thinking: "Recursion passes smaller and smaller strings"

New thinking: "Recursion passes the SAME string, but starts reading from different positions"

It's like a team of workers on an assembly line:

• Worker 1 (index=0): "I'll handle the first item, you handle the rest starting from position 1"
• Worker 2 (index=1): "I'll handle this item, you handle the rest starting from position 2"
• Worker 3 (index=2): "I'll handle... wait, there's nothing! We're done!" (base case)

---

Layer 14: Validation Question

For s = "226", when we're at decode(s, 1):

1. What character are we looking at?
2. What characters are we IGNORING?
3. Why can we ignore them?

Answer

1. Looking at: s.charAt(1) = '2'
2. Ignoring: s.charAt(0) = '2'
3. Why: Because the PREVIOUS recursive call (at index=0) already made a decision about what to do with s[0]. Our job is ONLY to handle s[1] onwards. The decision about s[0] is already baked into the path that led us here.

---

Layer 15: The Missing Insights (Prerequisites)

Insight #1: Why can I just sum the counts?

Because the paths are disjoint—taking 1 digit vs 2 digits leads to completely different subtrees. No double-counting.

Insight #2: Why does leading zero invalidate a path?

Because there's no letter mapped to "0", "00", "01", etc. The moment we encounter a position starting with '0', that entire branch is invalid.

Insight #3: Why check twoDigit <= 26 specifically?

Because 'Z' is the 26th letter. Anything above has no mapping.

Insight #4: Why check index + 1 < s.length()?

Prevents ArrayIndexOutOfBoundsException!

If we're at the last character, there's no second digit to grab. Java will crash if we try to access s.charAt(index + 1) when index + 1 >= s.length().

Example: If s = "226" and index = 2:

// At index 2 (last position):
if (index + 1 < s.length()) {  // 2 + 1 < 3? → 3 < 3? NO!
    // Skip - no second digit available
}

---

Layer 16: Visualizing the Recursion with Debug Output

Sometimes the best way to understand recursion is to see it in action. Here are two instrumented versions of our solution with print statements to visualize the execution flow.

Approach 1: Count-Based with Void Return

This version uses a void recursive function that increments a counter array when it finds a valid path.

class Solution {
    public int numDecodings(String s) {
        int[] count = new int[1];  // Using array so we can modify it in recursion
        decode(s, 0, count);
        return count[0];
    }

    private void decode(String s, int index, int[] count) {
        // SUCCESS! We found a complete valid decoding
        if (index == s.length()) {
            count[0]++;  // ← SEE IT INCREMENT HERE!
            System.out.println("✓ Found a valid path! Total ways so far: " + count[0]);
            return;
        }

        // FAILURE! Hit a leading zero
        if (s.charAt(index) == '0') {
            System.out.println("✗ Hit leading zero at index " + index + ", backtracking...");
            return;
        }

        // Choice 1: Take 1 digit
        System.out.println("Trying: Take 1 digit '" + s.charAt(index) + "' at index " + index);
        decode(s, index + 1, count);

        // 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) {
                System.out.println("Trying: Take 2 digits '" + twoDigit + "' at index " + index);
                decode(s, index + 2, count);
            }
        }
    }
}

Why Use int[] Instead of int?

In Java, primitive types (like int) are passed by value, meaning changes inside the function don't affect the original variable.

Arrays are passed by reference, so when we modify count[0], the change persists across all recursive calls!

This is a common trick for maintaining shared state in recursion.

Example Output for s = "12":

Trying: Take 1 digit '1' at index 0
Trying: Take 1 digit '2' at index 1
✓ Found a valid path! Total ways so far: 1
Trying: Take 2 digits '12' at index 0
✓ Found a valid path! Total ways so far: 2

---

Approach 2: Return-Based with Detailed Logging

This version uses our original return-based approach but adds detailed logging to show how values bubble up through recursion.

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

    private int decode(String s, int index) {
        // Base case: reached the end
        if (index == s.length()) {
            System.out.println("✓ Reached end! Returning 1");
            return 1;  // ← THIS IS WHERE WE COUNT A PATH
        }

        // Base case: leading zero
        if (s.charAt(index) == '0') {
            System.out.println("✗ Leading zero! Returning 0");
            return 0;  // ← THIS PATH IS INVALID
        }

        System.out.println("At index " + index + ", char: " + s.charAt(index));

        // Choice 1: Take 1 digit
        System.out.println("  Exploring: take 1 digit");
        int waysFromChoice1 = decode(s, index + 1);
        System.out.println("  Choice 1 returned: " + waysFromChoice1);

        int waysFromChoice2 = 0;

        // 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) {
                System.out.println("  Exploring: take 2 digits (" + twoDigit + ")");
                waysFromChoice2 = decode(s, index + 2);
                System.out.println("  Choice 2 returned: " + waysFromChoice2);
            }
        }

        int totalWays = waysFromChoice1 + waysFromChoice2;
        System.out.println("At index " + index + ": combining " + waysFromChoice1 + " + " + waysFromChoice2 + " = " + totalWays);

        return totalWays;
    }
}

Example Output for s = "12":

At index 0, char: 1
  Exploring: take 1 digit
At index 1, char: 2
  Exploring: take 1 digit
✓ Reached end! Returning 1
  Choice 1 returned: 1
At index 1: combining 1 + 0 = 1
  Choice 1 returned: 1
  Exploring: take 2 digits (12)
✓ Reached end! Returning 1
  Choice 2 returned: 1
At index 0: combining 1 + 1 = 2

Without Debug Logs (Clean Version)

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

    private int decode(String s, int index) {
        // Base case: reached the end
        if (index == s.length()) {
            return 1;
        }

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

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

        int waysFromChoice2 = 0;

        // 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) {
                waysFromChoice2 = decode(s, index + 2);
            }
        }

        int totalWays = waysFromChoice1 + waysFromChoice2;

        return totalWays;
    }
}

---

Comparing the Two Approaches

Aspect	Void with Counter	Return-Based
Return Type	void	int
State Management	External counter array	Return values bubble up
Mental Model	"Count valid endpoints"	"Sum valid paths"
Debugging	See counts increment	See values combine
Typical Use	DFS path enumeration	DP counting problems

Which Approach to Use?

Void with counter: Better when you want to collect or enumerate all valid paths/solutions

Return-based: Better when you want to count or compute aggregate values (sum, max, min)

For this problem, the return-based approach is more natural because we're computing a count through the recurrence relation.

---

The Beauty of Seeing It Run

Try It Yourself!

Copy either version and run it with different inputs:

• "12" - simple case
• "226" - three paths
• "06" - invalid leading zero
• "10" - edge case with zero

Watch how the recursion explores the decision tree and how values either increment (void approach) or combine (return approach)!

Learning Tip: Adding print statements to recursive code is one of the best ways to build intuition. You can see the decision tree unfold, watch base cases trigger, and observe how values propagate back up the call stack.

---

Meta-Process: The Framework

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)

---

Summary

Key Takeaways

1. ✅ State: decode(s, index) = number of ways to decode from index onwards
2. ✅ Choices: Take 1 digit OR take 2 digits (if valid)
3. ✅ Base cases:
   • index == length → return 1 (success)
   • s[index] == '0' → return 0 (invalid)
4. ✅ Valid two-digit range: 10-26, NOT 0-26
5. ✅ Index as cursor: Passes same string, different starting position
6. ✅ No substring creation: Efficient memory usage
7. ✅ Boundary check: index + 1 < length prevents crashes

Complexity:

• Time: O(2^n) - each position branches into 2 choices
• Space: O(n) - recursion depth

This unoptimized version explores the full decision tree and will be slow for large inputs. Next step: Add memoization to avoid recalculating the same subproblems!