MediumDynamic Programming

Decode Ways

Explanation & Solution

Description

A message containing letters from A-Z can be encoded into numbers using the mapping: 'A' = 1, 'B' = 2, ..., 'Z' = 26.

Given a string s containing only digits, return the number of ways to decode it. A digit sequence may have multiple valid decodings. For example, "11106" can be decoded as "AAJF" (1 1 10 6) or "KJF" (11 10 6). Note that "06" is not valid because "6" and "06" are different in the mapping.

Input: s = "12"

Output: 2

Explanation: "12" can be decoded as "AB" (1 2) or "L" (12).

Constraints

1 <= s.length <= 100
s contains only digits '0' through '9'

Approach

Dynamic Programming pattern

1. Handle the Base Case

If the string is empty or starts with '0', return 0 immediately — there is no valid decoding
Initialize prev2 = 1 (ways to decode empty prefix) and prev1 = 1 (ways to decode first character)

2. Iterate Through the String

For each position i from 1 to n - 1, compute curr — the number of ways to decode s[0..i]
Check two possibilities at each position: using one digit or two digits

3. Single Digit Check

Extract the single digit s[i]
If it is between 1 and 9, it maps to a valid letter, so add prev1 (ways to decode up to the previous position)
A '0' by itself is not a valid single-digit decoding

4. Two Digit Check

Extract the two-digit number formed by s[i-1] and s[i]
If it is between 10 and 26, it maps to a valid letter, so add prev2 (ways to decode up to two positions back)
Numbers like 07 or 30 do not form valid two-digit codes

5. Slide the Window Forward

Update prev2 = prev1 and prev1 = curr for the next iteration
After the loop, prev1 holds the total number of decodings for the entire string

Key Insight

This is a Fibonacci-like DP where each position depends on the previous one or two positions
The space-optimized approach uses only two variables instead of a full array, giving O(1) space
Time complexity is O(n) for a single pass through the string

Visualization

Input:

Dynamic Programmings = "12"

Press play to start DP animation

ComputingDependencyFilledEmpty

4 steps

Solution Code

Partition Equal Subset Sum

Unique Paths