🔢 LC 91: Decode Ways - First Principles Breakdown

The Designer's Mindset

Before jumping to code, ask yourself: "What decisions am I making at each point?"

This document reveals the messy, authentic thought process of discovering the recursive solution to Decode Ways.

---

1. Discovery & Problem Understanding

1.1 Problem Analysis & Discovery

What's the raw problem?

"Count the number of ways to split a string of digits into valid letter codes (1-26)."

The Messy Discovery Process

First instinct:

"This feels like... I have choices to make?"

At position 0 in "11106", I can take:

• Just "1" → then solve the rest "1106"
• Or "11" → then solve the rest "106"

💡 Aha moment #1

"Wait, this is a DECISION TREE problem!"

• At each position, I'm deciding: "Do I take 1 digit or 2 digits?"
• Each decision branches into subproblems
• The answer is counting ALL valid paths through this tree

But when can I make these choices?

• Taking 1 digit: Always valid? NO! "0" by itself is invalid
• Taking 2 digits: Always valid? NO! Must be between 10-26

1.2 Prerequisites & Key Insights

The Property That Makes This Problem "Countable"

The total ways to decode string s =

(ways if I take 1 digit) + (ways if I take 2 digits)

This is ADDITIVE COUNTING - when you have mutually exclusive choices, you ADD the counts.

Think of it like: "How many paths to the park?"

3 paths through the forest + 2 paths along the river = 5 total paths

1.3 Recursive Translation

What does recursion need?

1. The State: "What changes as I make decisions?"

• My position in the string (index)
• That's it! The string itself doesn't change.

2. The Base Case: "When do I stop recursing?"

if (index == s.length()) → return 1

• I've consumed all digits successfully → return 1 (this is ONE valid way)
• Why 1? Because reaching the end means the path I took was valid.

3. The Recursive Case: "What are my choices?"

At index i, I can:

1. Take 1 digit (if valid) → recurse from index i+1
2. Take 2 digits (if valid) → recurse from index i+2

Total ways = (ways from choice 1) + (ways from choice 2)

Why This Data Structure? (Just integers)

We only need:

• index: where we are in the string
• The count returned from subproblems

No arrays, no fancy structures. Why?

• We're not building the actual decodings (that would need storage)
• We're just COUNTING paths through a decision tree
• Each recursive call returns a number, we add them up

---

2. Implementation & Validation

2.1 Recursive Solution

class Solution {
    public int numDecodings(String s) {
        // Entry point: start from index 0
        return decode(s, 0);
    }

    /**
     * Recursively counts the number of ways to decode s starting from 'index'
     *
     * DESIGNER THOUGHT: "From this position, how many valid paths exist?"
     *
     * @param s The encoded string (never changes)
     * @param index Current position we're trying to decode from
     * @return Number of valid ways to decode from this position to the end
     */
    private int decode(String s, int index) {
        // BASE CASE: Reached the end successfully
        // THOUGHT: "I've used all digits without breaking any rules → 1 valid path"
        if (index == s.length()) {
            return 1;
        }

        // INVALID CASE: Current digit is '0'
        // THOUGHT: "0 can't stand alone, and I can't start a 2-digit code with 0"
        // Example: "01" or "301" - the '0' makes this path impossible
        if (s.charAt(index) == '0') {
            return 0;
        }

        // CHOICE 1: Take single digit
        // THOUGHT: "What if I decode just this one digit as a letter?"
        // Example: At "1106", taking "1" leaves "106" to solve
        int ways = decode(s, index + 1);

        // CHOICE 2: Take two digits (if possible)
        // THOUGHT: "Can I grab two digits and make a valid code (10-26)?"

        // First check: Do we even have 2 digits left?
        if (index + 1 < s.length()) {
            // Extract the two-digit number
            // Example: "11" at start of "11106" → twoDigit = 11
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));

            // Second check: Is it a valid letter code (10-26)?
            // THOUGHT: "11 is valid (K), but 27 would be invalid"
            if (twoDigit >= 10 && twoDigit <= 26) {
                // Add the ways from taking 2 digits
                ways += decode(s, index + 2);
            }
        }

        return ways;
    }
}

The Code Reads Like a Decision Tree

1. "Am I at the end?" → Base case returns 1
2. "Is current digit 0?" → Invalid, return 0
3. "Try taking 1 digit" → Recurse from next position
4. "Can I take 2 digits?" → Check validity and recurse
5. "Add up the counts" → Sum all valid paths

2.2 Edge Case Tracing

Tracing "11106" - The Tree of Decisions:

                    "11106" (start at index 0)
                    /                    \
            take "1"                    take "11"
                /                            \
        "1106" (idx=1)                   "106" (idx=2)
        /           \                    /          \
   take "1"      take "11"          take "1"     take "10"
      /              \                 /              \
  "106"(idx=2)    "06"(idx=3)      "06"(idx=3)    "6"(idx=4)
                     ❌                ❌              |
                (starts with 0)                  take "6"
                                                      |
  Continue...                                    ""(idx=5)
                                                     ✓ = 1

(Full trace continues, final answer: 2 ways)

Why does "06" fail?

• s.charAt(3) == '0' → We immediately return 0
• Concept validation: "Leading zeros are invalid because there's no letter mapping for '0' alone, and '06' ≠ '6'"

Edge Case: "10"

"10" (index=0)
  |
  '1' alone? → leaves "0" → "0" returns 0 ❌
  '10' together? → 10 is valid → leaves "" → return 1 ✓

Answer: 1 way

Why This Matters

Shows that even though '1' is valid alone, if it creates an impossible situation later, that branch dies.

But taking '10' together works!

Edge Case: "226"

"226" (index=0)
  /              \
take "2"       take "22"
  |                |
"26"(idx=1)    "6"(idx=2)
  /      \          |
take"2" take"26"  take"6"
  |        |        |
"6"     ""(idx=3)  ""
  |        ✓=1      ✓=1
take"6"
  |
""(idx=3)
  ✓=1

Total: 3 ways

The 3 decodings:

1. 2-2-6 → "BBF"
2. 2-26 → "BZ"
3. 22-6 → "VF"

2.3 Meta-Process Framework

How to Think Through ANY Counting Problem

Step 1: Identify the decision points

"Where do I have choices?"

Here: 1 digit or 2 digits at each position

Step 2: Define what makes a choice valid

"What are the constraints?"

Here: No leading zeros, two-digits must be 10-26

Step 3: Recognize the counting pattern

"How do I combine sub-counts?"

Here: Additive (choices are mutually exclusive paths)

Step 4: Find the state

"What do I need to know to solve a subproblem?"

Here: Just the current index

Step 5: Identify base cases

"When can I stop recursing?"

Here: Reached the end (success = 1), hit '0' (failure = 0)

---

3. Pattern Recognition & Mastery

3.1 Connecting to Prior Knowledge

Have you seen problems where:

• You count paths in a grid? (Same idea: add up paths from each direction)
• You count ways to climb stairs? (Same structure: 1 step or 2 steps)
• You make yes/no decisions and count outcomes? (Same branching logic)

This is the Same Pattern!

The "shape" of the recursion is:

count = (count from choice A) + (count from choice B) + ...

Pattern Recognition:

Problem	Choices at Each Step	How to Combine
Climbing Stairs	1 step or 2 steps	Add counts
Decode Ways	1 digit or 2 digits	Add counts
Coin Change II	Use coin or skip	Add counts

3.2 Self-Assessment Questions

Before we optimize, can you answer:

Q1: Why do we return 1 at the base case instead of 0?

Click to reveal answer

Answer

Because reaching the end successfully represents ONE complete valid path.

If we returned 0, we'd be saying "this path doesn't count," which is wrong. The recursion is counting paths, and each successful path to the end counts as 1.

Q2: What would happen if we removed the '0' check?

Click to reveal answer

Answer

We'd count invalid decodings!

For example, "106" would incorrectly allow:

• "1-0-6" (invalid because 0 can't be decoded alone)

The '0' check ensures we immediately reject paths that hit a standalone zero.

Q3: Why do we check index + 1 < s.length() before taking 2 digits?

Click to reveal answer

Answer

To prevent index out of bounds errors!

If we're at the last character, there's no second digit to take. Without this check, s.substring(index, index + 2) would throw an exception.

Example: At "12" with index=1, we can't take 2 digits from position 1.

Q4: How would the recursion tree change for "226"?

Click to reveal answer

Answer

See the edge case trace above! Key differences:

• More branching because all digits are non-zero
• Three valid complete paths (3 ways to decode)
• Both "22" and "26" are valid 2-digit codes

3.3 Evolution Path & Takeaways

The Complete Evolution Path

Evolution 1: Pure Recursion (Current - Understanding)

// Time: O(2^n) - exponential, overlapping subproblems
// Space: O(n) - recursion stack depth
decode(s, index) {
    if (index == s.length()) return 1;
    if (s[index] == '0') return 0;

    ways = decode(s, index + 1);
    if (canTake2Digits) ways += decode(s, index + 2);
    return ways;
}

Evolution 2: Memoization (Top-Down DP - Next Step)

// Time: O(n) - each index computed once
// Space: O(n) - memo array + recursion stack
Integer[] memo = new Integer[n];
if (memo[index] != null) return memo[index];
// ... same logic ...
memo[index] = ways;
return ways;

Evolution 3: Bottom-Up DP (Iteration)

// Time: O(n)
// Space: O(n) - dp array only
int[] dp = new int[n + 1];
dp[n] = 1; // base case
for (int i = n - 1; i >= 0; i--) {
    // ... build from smaller subproblems ...
}

Evolution 4: Space Optimization

// Time: O(n)
// Space: O(1) - only track last 2 values
int curr, prev1 = 1, prev2 = 0;
for (int i = n - 1; i >= 0; i--) {
    // ... use prev1 and prev2 ...
}

Key Takeaways

1. ✅ Counting problems use ADDITIVE logic - mutually exclusive choices are summed
2. ✅ Base case returns the count unit - here it's 1 (one valid path)
3. ✅ Invalid cases return 0 - they contribute nothing to the count
4. ✅ State is minimal - only track what changes (index)
5. ✅ Constraints become conditionals - check validity before recursing

The Core Insight

This isn't about building solutions - it's about counting paths through a decision tree.

Every valid path from start to end represents one way to decode the string. Our recursion explores all paths and counts the valid ones.

Next Steps

Once you've internalized WHY this recursive solution works:

1. Add memoization - Cache results to avoid recomputation
2. Convert to bottom-up - Iterative DP for better space
3. Optimize space - Reduce to O(1) by tracking only what's needed
4. Practice similar problems - Climbing Stairs, Fibonacci, Coin Change II

The Journey Continues

You now understand the recursive foundation of Decode Ways!

Every DP optimization builds on this core recursive structure. Master the recursion first, optimize second. 🚀