91. Decode Ways - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0

        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1

        for i in range(2, n + 1):
            one_digit = int(s[i - 1:i])
            two_digits = int(s[i - 2:i])

            if 1 <= one_digit <= 9:
                dp[i] += dp[i - 1]
            if 10 <= two_digits <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

Java

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

        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            int oneDigit = Integer.parseInt(s.substring(i - 1, i));
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));

            if (oneDigit >= 1) {
                dp[i] += dp[i - 1];
            }
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

C++

#include <string>
#include <vector>

int numDecodings(std::string s) {
    if (s.empty() || s[0] == '0') return 0;
    int n = s.size();
    std::vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        if (s[i - 1] != '0') {
            dp[i] += dp[i - 1];
        }
        int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (twoDigit >= 10 && twoDigit <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

JavaScript

var numDecodings = function(s) {
    if (!s || s[0] === '0') return 0;
    let n = s.length;
    let dp = Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        let oneDigit = parseInt(s.substring(i - 1, i));
        let twoDigits = parseInt(s.substring(i - 2, i));

        if (oneDigit >= 1) {
            dp[i] += dp[i - 1];
        }
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[n];
};

#include <string.h>

int numDecodings(char * s) {
    if (s[0] == '0') return 0;
    int n = strlen(s);
    int dp[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = 0;
        int oneDigit = s[i - 1] - '0';
        int twoDigits = (s[i - 2] - '0') * 10 + oneDigit;

        if (oneDigit >= 1) {
            dp[i] += dp[i - 1];
        }
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

using System;

public class Solution {
    public int NumDecodings(string s) {
        if (s == null || s.Length == 0 || s[0] == '0') return 0;

        int n = s.Length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            int oneDigit = int.Parse(s.Substring(i - 1, 1));
            int twoDigits = int.Parse(s.Substring(i - 2, 2));

            if (oneDigit >= 1) {
                dp[i] += dp[i - 1];
            }
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

In Python, slicing and conversion to integer make it easy to work with substrings while dynamically updating the number of decoding ways.

The use of arrays is straightforward and supports clearer indexing using Python's dynamic typing system.

Complexity

Time Complexity: O(n) due to a single pass traversal through the string.

Space Complexity: O(n), given the utilization of a list to store dp results.

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.

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0

        n = len(s)
        prev1, prev2 = 1, 1

        for i in range(1, n):
            current = 0
            one_digit = int(s[i])
            two_digits = int(s[i-1:i+1])

            if 1 <= one_digit <= 9:
                current += prev1
            if 10 <= two_digits <= 26:
                current += prev2

            prev2 = prev1
            prev1 = current

        return prev1

Java

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

        int n = s.length();
        int prev1 = 1, prev2 = 1;

        for (int i = 1; i < n; i++) {
            int current = 0;
            int oneDigit = Integer.parseInt(s.substring(i, i + 1));
            int twoDigits = Integer.parseInt(s.substring(i - 1, i + 1));

            if (oneDigit >= 1) {
                current += prev1;
            }
            if (twoDigits >= 10 && twoDigits <= 26) {
                current += prev2;
            }
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

C++

#include <string>

int numDecodings(std::string s) {
    if (s.empty() || s[0] == '0') return 0;
    int n = s.size();
    int prev1 = 1, prev2 = 1;

    for (int i = 2; i <= n; i++) {
        int current = 0;
        if (s[i - 1] != '0') {
            current += prev1;
        }
        int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (twoDigit >= 10 && twoDigit <= 26) {
            current += prev2;
        }
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

JavaScript

var numDecodings = function(s) {
    if (!s || s[0] === '0') return 0;
    let n = s.length;
    let prev1 = 1, prev2 = 1;

    for (let i = 1; i < n; i++) {
        let current = 0;
        let oneDigit = parseInt(s[i]);
        let twoDigits = parseInt(s.slice(i - 1, i + 1));

        if (oneDigit >= 1) {
            current += prev1;
        }
        if (twoDigits >= 10 && twoDigits <= 26) {
            current += prev2;
        }
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
};

#include <string.h>

int numDecodings(char * s) {
    if (s[0] == '0') return 0;
    int n = strlen(s), prev2 = 1, prev1 = 1;

    for (int i = 2; i <= n; i++) {
        int current = 0;
        int oneDigit = s[i - 1] - '0';
        int twoDigits = (s[i - 2] - '0') * 10 + oneDigit;

        if (oneDigit >= 1) {
            current += prev1;
        }
        if (twoDigits >= 10 && twoDigits <= 26) {
            current += prev2;
        }
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

using System;

public class Solution {
    public int NumDecodings(string s) {
        if (s == null || s.Length == 0 || s[0] == '0') return 0;

        int n = s.Length, prev1 = 1, prev2 = 1;

        for (int i = 1; i < n; i++) {
            int current = 0;
            int oneDigit = int.Parse(s[i].ToString());
            int twoDigits = int.Parse(s.Substring(i - 1, 2));

            if (oneDigit >= 1) {
                current += prev1;
            }
            if (twoDigits >= 10 && twoDigits <= 26) {
                current += prev2;
            }
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

Utilizing Python's intuitive dynamic nature, two variables maintain preceding results to support ongoing calculations without resorting to expansive memory utilization.

Holding results to adjacent indices allow dynamic inter-update operations with a fixed space guarantee.

Complexity

Time Complexity: O(n) with direct single pass across the string length.

Space Complexity: O(1), deploying only constant space for ongoing solution derivation.

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.

TypeScript

function numDecodings(s: string): number {
    const n = s.length;
    const f: number[] = new Array(n + 1).fill(0);
    f[0] = 1;
    for (let i = 1; i <= n; ++i) {
        if (s[i - 1] !== '0') {
            f[i] = f[i - 1];
        }
        if (i > 1 && (s[i - 2] === '1' || (s[i - 2] === '2' && s[i - 1] <= '6'))) {
            f[i] += f[i - 2];
        }
    }
    return f[n];
}

func numDecodings(s string) int {
	n := len(s)
	f := make([]int, n+1)
	f[0] = 1
	for i := 1; i <= n; i++ {
		if s[i-1] != '0' {
			f[i] = f[i-1]
		}
		if i > 1 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) {
			f[i] += f[i-2]
		}
	}
	return f[n]
}

Try this approach in the editor

Complexity comparison

Approach Complexity

Dynamic Programming Approach

Approach	Complexity
Dynamic Programming Approach	Time Complexity: `O(n)` due to a single pass traversal through the string. Space Complexity: `O(n)`, given the utilization of a list to store dp results.
Optimized Space Dynamic Programming Approach	Time Complexity: `O(n)` with direct single pass across the string length. Space Complexity: `O(1)`, deploying only constant space for ongoing solution derivation.
Dynamic Programming	–

Time Complexity: O(n) due to a single pass traversal through the string.

Space Complexity: O(n), given the utilization of a list to store dp results.

Optimized Space Dynamic Programming Approach

Time Complexity: O(n) with direct single pass across the string length.

Space Complexity: O(1), deploying only constant space for ongoing solution derivation.

Dynamic Programming –

Complexity analysis

Approach	Time	Space	When to Use
Recursive Exploration	O(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 DP	O(n)	O(1)	Interview-preferred solution when memory efficiency matters

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.

Decode Ways solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Optimized Space Dynamic Programming Approach

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Decode Ways solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Optimized Space Dynamic Programming Approach

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems