The O(n) Club: Decode Ways — How Zeros Spoil All Your Fun (and DP Saves You)

The O(n) Club: Decode Ways — How Zeros Spoil All Your Fun (and DP Saves You)

⚡ TL;DR

Given a string of digits, count all the ways to map it to A-Z, where ‘A’ = ‘1’, …, ‘Z’ = ’26’. Sure, brute force is tempting—right until you hit a timeout and question your career choices.

// Brute force regret in Java
int numDecodings(String s) {
    if (s.isEmpty() || s.charAt(0) == '0') return 0;
    return helper(s, 0);
}
int helper(String s, int idx) {
    if (idx == s.length()) return 1;
    if (s.charAt(idx) == '0') return 0;
    int cnt = helper(s, idx + 1);
    if (idx + 1 < s.length() && Integer.parseInt(s.substring(idx, idx+2)) <= 26 && s.charAt(idx) != '0')
        cnt += helper(s, idx + 2);
    return cnt;
}

🧠 How Devs Usually Mess This Up

Newbies (and sleep-deprived seniors) love to ignore zeros—until “06” ruins their day or they try to decode ‘0’ solo like some rebel ninja. Others gleefully pair up any two digits—except ’27’ and friends don’t count. Bonus points if you forget to treat empty strings or leading zeros as hard fails. Oh, and don’t forget the off-by-one bug for that genuine Leetcode experience!

🔍 What’s Actually Going On

Picture string decoding as crossing a rickety bridge: each plank is a digit. You can skip forward by one (if your plank isn’t a zero-shaped hole in the bridge), or leap two if the pair is ’10’ to ’26’. Anything else and you’re taking a swim. Dynamic Programming ties a safety net under every possible path; each step builds off past steps, like a chef prepping ingredients before assembling the dish. ‘dp[i]’ contains the number of ways to decode up to that point—just add up the safe pathways!

🛠️ PseudoCode

• Start checks:
  

  if (s is empty OR s[0] == '0') return 0;
  dp[0] = 1
  dp[1] = 1

  If your string starts with disaster (‘0’), bail out now. Otherwise, set up the warm-up dp entries.

• Walk through the string:

  for i = 2 to n:
    if (s[i-1] != '0') dp[i] += dp[i-1]; // single digit
    if (10 <= twoDigit && twoDigit <= 26) dp[i] += dp[i-2]; // valid pair
  

  At every index: can you step here from one back? Two back? (Assuming passages are open!)

• Return answer:

  return dp[n];

  Because you only count successful crossings.

💻 The Code

public int numDecodings(String s) {
    if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
    int n = s.length();
    int[] dp = new int[n+1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        // Lone digit
        if (s.charAt(i-1) != '0') dp[i] += dp[i-1];
        // Pair
        int val = Integer.parseInt(s.substring(i-2, i));
        if (val >= 10 && val <= 26) dp[i] += dp[i-2];
    }
    return dp[n];
}

Psst: Want O(1) space? It’s just juggling two ints—like speedrunning array DP with less RAM.

⚠️ Pitfalls, Traps & Runtime Smacks

• Lone Zeros: ‘0’ must be glued to ‘1’ or ‘2’. Anywhere else is a bug.
• Pairs Over 26: ‘27’ loves to pretend it has friends, but it doesn’t.
• Input ‘100’: Only “10 0” is valid, but ‘0’ can’t stand alone. (Only 1 way: “J”)
• Complexity: O(n) time, O(n) space—or O(1) if you pack light. Either way, runtime’s not the reason you fail an interview here!

🧠 Interviewer Brain-Tattoo

Every zero in a string is either your best bud (’10’, ’20’) or instant sabotage. Trust but verify—and let DP do the heavy lifting before your brain melts.