Problem Statement

Given a digit string, count how many ways it can be decoded using mapping 1→A, ..., 26→Z.

Why This Problem Matters

• Teaches string DP with conditional transitions.
• Common interview favourite requiring careful handling of zeros.
• Builds intuition for DP on sequences with local dependencies.

Thought Process

Step-by-Step Reasoning

1. Initialise dp array length n + 1 with dp[0] = 1.
2. Set dp[1] based on whether first char != 0.
3. For i from 2..n compute oneDigit = s[i-1], twoDigit = s[i-2..i-1]; accumulate valid transitions.
4. Return dp[n].

Dry Run

Complexity Analysis

Annotated Solution

public class DecodeWays {
  public int numDecodings(String s) {
    if (s == null || s.length() == 0 || s.charAt(0) == '0') {
      return 0;
    }

    int prev2 = 1;
    int prev1 = 1;

    for (int i = 1; i < s.length(); i += 1) {
      int current = 0;
      char c = s.charAt(i);
      if (c != '0') {
        current += prev1;
      }
      int twoDigit = (s.charAt(i - 1) - '0') * 10 + (c - '0');
      if (twoDigit >= 10 && twoDigit <= 26) {
        current += prev2;
      }
      if (current == 0) {
        return 0;
      }
      prev2 = prev1;
      prev1 = current;
    }

    return prev1;
  }
}

Rolling variables track dp[i-1] and dp[i-2]; zeros contribute only through valid two-digit combinations.

Common Pitfalls

• Treating zero as decodable alone; only works with 10 or 20 pairings.
• Failing to use integers for two-digit substring; string comparisons more error-prone.
• Accessing s.charAt(i-2) when i < 2 causes index errors.

Follow-Up Questions

• How would the mapping change if * wildcard digits were allowed? (See Decode Ways II.)
• Can you output all decodings instead of counting them? (Backtracking with pruning.)

Key Takeaways