Skip to main content
Talentd

Decode Ways - Solution & Explanation

MediumStringDynamic Programming18 min readAsked at: Amazon, Microsoft, Apple +19
Practice this problem

Problem Statement

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

  • "AAJF" with the grouping (1, 1, 10, 6)
  • "KJF" with the grouping (11, 10, 6)
  • The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

Input: s = "12"

Output: 2

Explanation:

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"

Output: 3

Explanation:

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "06"

Output: 0

Explanation:

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

 

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

Approach Overview

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.

Approach 1: Dynamic Programming Approach

The dynamic programming approach leverages the fact that a problem can be broken into subproblems. Here, we use an array dp where dp[i] represents the number of ways to decode the substring s[0..i-1].

We iterate through the string and update the dp array based on the valid single and two-digit mappings.

In this C solution, we use an integer array dp to store the number of ways to decode the string up to each character.

We initialize dp[0] = 1 as there's one way to decode an empty string, and dp[1] = 1 because there's one way to decode a valid single character (assuming it's not '0'). We then loop through the string starting from the second character, calculating the number of ways to decode it based on one-digit and two-digit combinations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input string. This is because we iterate over each character once.

Space Complexity: O(n), as we use an additional array of size n for storing our results for subproblems.

Try this approach in the editor →

Approach 2: Optimized Space Dynamic Programming Approach

Instead of using an entire array to store all previous results, this approach keeps track of only the last two computations (since we only ever need the last two values for our dp computations).

Thus, we use two variables to hold these values and update them as needed to keep our space usage minimal.

This C solution reduces space complexity by using two variables - prev1 and prev2 to keep track of decodings without maintaining a full dp array.

These variables capture prior computations needed for the current index advance.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), since each character in the string is touched once.

Space Complexity: O(1), because only two variables are used to maintain state.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i] to represent the number of decoding methods for the first i characters of the string. Initially, f[0]=1, and the rest f[i]=0.

Consider how f[i] transitions.

  • If the ith character (i.e., s[i-1]) forms a code on its own, it corresponds to one decoding method, i.e., f[i]=f[i-1]. The premise is s[i-1] neq 0.
  • If the string formed by the i-1th character and the ith character is within the range [1,26], then they can be treated as a whole, corresponding to one decoding method, i.e., f[i] = f[i] + f[i-2]. The premise is s[i-2] neq 0, and s[i-2]s[i-1] is within the range [1,26].

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n), where n is the length of the input string. This is because we iterate over each character once.

Space Complexity: O(n), as we use an additional array of size n for storing our results for subproblems.

Optimized Space Dynamic Programming Approach

Time Complexity: O(n), since each character in the string is touched once.

Space Complexity: O(1), because only two variables are used to maintain state.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive ExplorationO(2^n)O(n)Conceptual understanding of all decoding combinations
Dynamic Programming (DP Array)O(n)O(n)General solution when clarity is preferred over memory optimization
Optimized Space DPO(n)O(1)Interview-preferred solution when memory efficiency matters

Video Solution

Decode Ways - Dynamic Programming - Leetcode 91 - Python • NeetCode • 298,056 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Decode Ways easy or hard?
Decode Ways is generally classified as a medium-level problem. The challenge comes from handling edge cases such as zeros and recognizing the dynamic programming relationship between adjacent positions in the string.
How to solve Decode Ways in O(n)?
Use dynamic programming and scan the string from left to right. At each index, add decoding counts from the previous position if the current digit is valid, and from two positions back if the two-digit number forms a valid mapping between 10 and 26. Maintaining only the last two states achieves O(n) time with constant space.
What is the best approach for Decode Ways?
Dynamic programming with constant space is the best approach. Iterate through the string and track the number of ways to decode up to the previous one and two positions. Each step checks valid single-digit and two-digit mappings between 10 and 26. This runs in O(n) time and O(1) space.
What data structure is used in Decode Ways?
The primary structure is a dynamic programming state, typically implemented as an array or two rolling variables. The algorithm operates directly on the input string while storing counts of valid decodings for previous positions.
What is the time complexity of Decode Ways?
The optimal solution runs in O(n) time where n is the length of the digit string. Each character is processed once while checking at most two decoding options. Space complexity can be O(n) with a DP array or reduced to O(1) using two variables.
Decode Ways Python or Java solution approach?
Both Python and Java implementations follow the same dynamic programming recurrence. Track ways to decode up to the previous index and the index before it, then update based on whether the current digit or the last two digits form valid mappings. The algorithm runs in O(n) time and O(1) space.
Is Decode Ways asked at Google, Amazon, or Meta?
Decode Ways is a common dynamic programming interview problem and has appeared in interviews at companies like Amazon, Google, and Meta. It tests recognition of overlapping subproblems, state transitions, and edge cases involving invalid numeric combinations.

Ready to solve this problem?

Practice Decode Ways with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Texts

Next

Decode Ways II