🗓️ Day 37: Decode Ways — DP on Strings with Numbers

🧠 Concept Deep Dive

You are given a string s containing only digits. Each digit or pair of digits can represent a letter ('1' = A, ..., '26' = Z). Your task: count the number of ways to decode s.

We will use Dynamic Programming where dp[i] represents the number of ways to decode up to index i.

🎯 Visual Intuition

Let’s say:

s = "226"

Can be split as "2 2 6" → B B F
Or "22 6" → V F
Or "2 26" → B Z

So 3 ways in total.

We’ll walk the string and for each position:

Add ways from previous if single digit is valid (1-9)
Add ways from previous two digits if valid (10–26)

🛠️ Code Pattern: DP with String

function numDecodings(s: string): number {
  if (!s || s[0] === '0') return 0;
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1; // empty string
  dp[1] = 1; // first char guaranteed not '0'

  for (let i = 2; i <= n; i++) {
    const one = Number(s.slice(i - 1, i));
    const two = Number(s.slice(i - 2, i));

    if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }
  return dp[n];
}

📘 Example

Input: s = "12"
Output: 2
Explanation: "AB" (1 2) or "L" (12)

Input: s = "226"
Output: 3
Explanation: "BBF", "BZ", "VF"

Input: s = "06"
Output: 0

🧪 Homework

What if s contains invalid characters like letters?
Modify the solution to also return one actual decoding path (any).
Solve using recursion + memoization.

🧠 Big-O Cheat Sheet

Time: O(n)
Space: O(n) — can be optimized to O(1) using two variables instead of an array

🔮 Up Next

▶️ Day 38: Palindrome Partitioning — All Ways to Split