Decode Ways

• Difficulty: Medium
• Topics: String, Dynamic Programming
• Link: https://leetcode.com/problems/decode-ways/

Problem Description

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = “12”

Output: 2

Explanation:

“12” could be decoded as “AB” (1 2) or “L” (12).

Example 2:

Input: s = “226”

Output: 3

Explanation:

“226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Example 3:

Input: s = “06”

Output: 0

Explanation:

“06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”). In this case, the string is not a valid encoding, so return 0.

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Solution

1. Problem Deconstruction

Technical Restatement
Given a string s of digits, determine the number of valid ways to partition s into substrings where each substring represents a number in [1,26], with no leading zeros. Return the count of such partitions or 0 if impossible.

Beginner-Friendly Explanation
You have a number string, and each number (1-26) can be turned into a letter. But some numbers can be split into smaller valid numbers. For example, “12” can be “1”+“2” (AB) or “12” (L). Find how many valid ways exist to split the string into such numbers. If no valid splits exist, return 0.

Mathematical Formulation
Let s be a string of length n. Let f(i) be the number of valid decodings for the first i characters. Recurrence:

• If s[i-1] ≠ '0', f(i) += f(i-1)
• If i ≥ 2 and 10 ≤ s[i-2:i] ≤ 26, f(i) += f(i-2)
  Base cases: f(0) = 1, f(1) = 1 if s[0] ≠ '0', else 0.
  Return f(n).

Constraint Analysis

1. 1 ≤ s.length ≤ 100:
   • Permits O(n) solutions but prohibits O(2ⁿ) brute force.
   • Edge cases: single-character strings (e.g., “0” → invalid).
2. Leading zeros:
   • Substrings like “06” are invalid despite “6” being valid.
   • Edge case: entire string starts with ‘0’ → output 0.
3. 32-bit integer output:
   • No overflow handling needed in code.

---

2. Intuition Scaffolding

Real-World Analogy
Imagine deciphering a locked treasure map where each number corresponds to a step. Some steps require two numbers (like 10-26), while others use one (1-9). The challenge is to count all valid paths without missteps (invalid codes).

Gaming Analogy
Like navigating a grid where each move is 1 or 2 tiles, but 2-tile moves are allowed only if the combined tile number is 10-26. How many paths reach the end?

Math Analogy
A modified Fibonacci sequence where each term depends on the previous 1 or 2 terms, conditioned on validity checks.

Common Pitfalls

1. Ignoring leading zeros: Treating “0” as valid (must return 0).
2. Overcounting invalid pairs: Not checking if two-digit numbers are in [10,26].
3. Base case errors: Missing f(0)=1 for empty string base case.
4. Off-by-one errors: Incorrectly indexing the string in DP transitions.
5. Greedy missteps: Assuming optimal splits without backtracking (e.g., always taking two digits when possible).

---

3. Approach Encyclopedia

Dynamic Programming (Optimal)

• Key Insight: Overlapping subproblems (number of ways to decode s[0..i] depends on previous substrings).
• Pseudocode:

  def numDecodings(s):
      n = len(s)
      dp = [0]*(n+1)
      dp[0] = 1  # Empty string has 1 way (base case)
      dp[1] = 0 if s[0] == '0' else 1
      for i in range(2, n+1):
          # Single-digit check
          if s[i-1] != '0':
              dp[i] += dp[i-1]
          # Two-digit check
          two_digit = int(s[i-2:i])
          if 10 <= two_digit <= 26:
              dp[i] += dp[i-2]
      return dp[n]
  

• Complexity:
  • Time: O(n) → Iterate through the string once.
  • Space: O(n) → DP array of size n+1.
• Visualization:

  i=0: [1, 0, 0, 0]  
  i=1: [1, 1, 0, 0]  
  i=2: [1, 1, 2, 0]  (e.g., "12" → 2 ways)  
  i=3: [1, 1, 2, 3]  (e.g., "226" → 3 ways)  
  

---

4. Code Deep Dive

Line-by-Line Explanation

def numDecodings(s: str) -> int:
    if not s:  # Handle empty input (constraints say 1<=n, but defensive)
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: 1 way to decode empty string
    dp[1] = 0 if s[0] == '0' else 1  # First character validity
    for i in range(2, n + 1):
        # Check single-digit validity (s[i-1] is current char)
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        # Check two-digit validity (s[i-2:i])
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
    return dp[n]

• Edge Cases:
  • Example 3 (“06”): dp[1]=0 (starts with ‘0’), dp[2] adds 0 from single-digit and 0 from two-digit → returns 0.
  • Leading Zero: s = "0" → dp[1] = 0 → output 0.
  • Valid Two-Digit: s = "10" → dp[2] = dp[0] = 1 → output 1.

---

5. Complexity War Room

Hardware Considerations

• For n=100, DP array uses ~400 bytes (100 integers) → negligible memory.
• Iterative approach leverages CPU cache efficiently (sequential access).

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(2ⁿ)	O(n)	6/10	❌ Fails n=100
Memoization	O(n)	O(n)	7/10	✅
DP (Optimal)	O(n)	O(n)	9/10	✅ Preferred

---

6. Pro Mode Extras

Variants

• LC 639 (Decode Ways II): Adds wildcard ‘*’ characters, requiring modular arithmetic.
• LC 123 (Two Transactions): Restrict to two splits, track state for buys/sells.

Interview Tips

• Mention Time/Space First: Interviewers prioritize efficiency awareness.
• Test Edge Cases: Always check leading zeros, single/double-digit validity.
• Optimization Insight: Note that space can be optimized to O(1) using variables for dp[i-1] and dp[i-2].