Decode Ways - Video Solutions

Problem Overview: You receive a string of digits where 1-26 map to letters A-Z. The task is to count how many valid ways the string can be decoded. A single digit may form a letter (1 → A) and certain pairs can form another (10 → J, 26 → Z). Invalid patterns like leading 0 or 30 must be ignored.

Approach 1: Recursive Exploration (Exponential Time)

Start at index 0 and recursively try decoding one digit or two digits if the pair forms a number between 10 and 26. Each recursive call advances the pointer and counts valid decoding paths until the end of the string. This brute-force tree explores all combinations of splits. Time complexity is O(2^n) in the worst case because each position can branch into two choices. Space complexity is O(n) due to recursion depth. This approach clarifies the structure of the problem but quickly becomes too slow for longer strings.

Approach 2: Dynamic Programming (O(n) time, O(n) space)

Dynamic programming removes repeated work from recursion. Create a dp array where dp[i] represents the number of ways to decode the prefix ending at index i. For each position, check two possibilities: decoding the current digit alone (valid if it's not 0) and decoding the last two digits together (valid if the number is between 10 and 26). Update dp[i] by adding contributions from dp[i-1] and dp[i-2]. The algorithm scans the string once, making it O(n) time with O(n) space. This is the standard solution using dynamic programming on a string.

Approach 3: Optimized Space Dynamic Programming (O(n) time, O(1) space)

The DP transition only depends on the previous two states: dp[i-1] and dp[i-2]. Instead of storing the entire array, keep two variables representing those values and update them while iterating through the string. At each step, compute the current count based on valid single-digit and two-digit decodings. This reduces memory usage to constant space while preserving the same O(n) time complexity. The technique is a common optimization pattern in dynamic programming when only a small window of previous states is required.

Recommended for interviews: The optimized dynamic programming approach is the expected answer. Interviewers want to see that you recognize overlapping subproblems, build a recurrence relation, and then reduce the DP state to constant space. Starting with the recursive idea shows understanding of the problem structure, but implementing the O(n) DP demonstrates strong problem-solving skills.