Decode Ways

Decode Ways

What is this problem about?

The Decode Ways interview question asks you to find the total number of ways a string of digits can be decoded into English letters. The mapping is standard: 'A' -> "1", 'B' -> "2" ... 'Z' -> "26". For example, "12" could be decoded as "AB" (1, 2) or "L" (12). However, strings starting with '0' (like "06") cannot be mapped, and values like "27" exceed the alphabet range. This Decode Ways coding problem is a test of state-based counting.

Why is this asked in interviews?

This is a classic problem at companies like Google, Meta, and Microsoft. It evaluates your ability to handle multiple edge cases (specifically the digit '0') and whether you can optimize a recursive solution using Dynamic Programming. It’s a slightly more complex version of the "Climbing Stairs" problem, as the number of steps you can take (1 or 2 digits) depends on the values of those digits.

Algorithmic pattern used

This follows the String, Dynamic Programming interview pattern.

1. State: dp[i] represents the number of ways to decode the prefix of the string of length i.
2. Base Case: dp[0] = 1 (one way to decode an empty string).
3. Transitions:
   • For each digit s[i-1] (single-digit mapping): If it's not '0', add dp[i-1] to dp[i].
   • For each pair s[i-2, i-1] (two-digit mapping): If the value is between "10" and "26", add dp[i-2] to dp[i].

Example explanation

Input: "226"

1. dp[0] = 1.
2. dp[1] ("2"): Valid single digit ('2'). dp[1] = dp[0] = 1.
3. dp[2] ("22"):
   • Single: '2' is valid. Add dp[1] -> 1.
   • Double: "22" is valid (between 10-26). Add dp[0] -> 1.
   • Total: 1 + 1 = 2. (Ways: "BB", "V").
4. dp[3] ("226"):
   • Single: '6' is valid. Add dp[2] -> 2.
   • Double: "26" is valid. Add dp[1] -> 1.
   • Total: 2 + 1 = 3. (Ways: "BBF", "VF", "BZ").

Common mistakes candidates make

• Ignoring '0': Forgetting that '0' cannot stand alone and cannot be the first digit of a two-digit number (e.g., "06" is invalid).
• Sub-optimal Space: Using a full dp array when you only ever need the last two values (O(1) space optimization).
• Time Complexity: Using recursion without memoization (O(2^N)), which times out for long strings.

Interview preparation tip

Always walk through an example containing '0' (like "10" or "2101"). It is the most common source of bugs in this problem and will show the interviewer you are detail-oriented.