91. Decode Ways - Explanation

Description

A string consisting of uppercase english characters can be encoded to a number using the following mapping:

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

To decode a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, "1012" can be mapped into:

"JAB" with the grouping (10 1 2)
"JL" with the grouping (10 12)

The grouping (1 01 2) is invalid because 01 cannot be mapped into a letter since it contains a leading zero.

Given a string s containing only digits, return the number of ways to decode it. You can assume 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 = "01"

Output: 0

Explanation: "01" cannot be decoded because "01" cannot be mapped into a letter.

Constraints:

1 <= s.length <= 100
s consists of digits

Topics

String Dynamic Programming

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the length of the given string.

Hint 1

The characters A through Z are mapped to the numbers from 1 to 26. A mapped number can have at most 2 digits. In the given string of digits, we can explore all possible decodings by combining one or two consecutive digits. Think of this in terms of a decision tree and explore all paths. Can you derive a recurrence relation for this?

Hint 2

Iterate over the string with index i. At each index, we have two choices: decode the current digit as a character with its mapped value, or combine the current digit with the next digit to form a two-digit value. The recurrence relation can be expressed as dfs(i + 1) + dfs(i + 2) where dfs is the recursive function. Also, consider edge cases, as not every two-digit number or a number with a leading zero is valid. How would you implement this?

Hint 3

A brute-force recursive solution would result in O(2^n) time complexity. Can you think of a better way? Perhaps you should consider the repeated work of calling the recursion multiple times with the same parameter values and find a way to avoid this. Also, can you think about the base condition of this recursive function?

Hint 4

The base condition is to return 1 if i goes out of bounds. If the current digit is '0', return 0, as no character maps to '0', making the string invalid. Use memoization to avoid repeated work by caching recursion results in an array or hash map and returning the stored value when the result is already calculated.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion - Breaking down problems into smaller subproblems by making recursive function calls
Dynamic Programming - Using memoization to cache results and avoid redundant computation
String Manipulation - Parsing and extracting substrings, character comparisons

1. Recursion

Intuition

Each digit (or pair of digits) in the string can be mapped to a letter:

"1" → "A", "2" → "B", …, "26" → "Z"

At any index i, you only have two possible decoding choices:

Take one digit (s[i]) → valid if it’s not '0'
Take two digits (s[i:i+2]) → valid if it forms a number between 10 and 26

So the problem naturally breaks into subproblems:

“How many ways can I decode the substring starting at index i?”

This leads directly to a recursive structure.

Key base ideas:

If you reach the end of the string → 1 valid decoding
If a substring starts with '0' → 0 ways (invalid)
Otherwise, sum the ways from:
- decoding one digit
- decoding two digits (if valid)

Algorithm

Define a recursive function dfs(i) = number of ways to decode s[i:].
Base cases:
- If i == len(s), return 1 (successfully decoded entire string).
- If s[i] == '0', return 0 (invalid decoding).
Recursively:
- Always try decoding one digit → dfs(i + 1)
- If two digits form a valid number (10-26), also try → dfs(i + 2)
Return the sum of valid choices.
Start recursion from index 0.

class Solution:
    def numDecodings(self, s: str) -> int:

        def dfs(i):
            if i == len(s):
                return 1
            if s[i] == '0':
                return 0

            res = dfs(i + 1)
            if i < len(s) - 1:
                if (s[i] == '1' or
                   (s[i] == '2' and s[i + 1] < '7')):
                    res += dfs(i + 2)

            return res

        return dfs(0)

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    numDecodings(s) {
        const dfs = (i) => {
            if (i === s.length) return 1;
            if (s[i] === '0') return 0;

            let res = dfs(i + 1);
            if (i < s.length - 1) {
                if (s[i] === '1' || (s[i] === '2' && s[i + 1] < '7')) {
                    res += dfs(i + 2);
                }
            }
            return res;
        };

        return dfs(0);
    }
}

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

            int res = Dfs(i + 1);
            if (i < s.Length - 1) {
                if (s[i] == '1' ||
                   (s[i] == '2' && s[i + 1] < '7')) {
                    res += Dfs(i + 2);
                }
            }
            return res;
        }

        return Dfs(0);
    }
}

class Solution {
    fun numDecodings(s: String): Int {
        return dfs(s, 0)
    }

    fun dfs(s: String, i: Int): Int {
        if (i == s.length) {
            return 1
        }
        if (s[i] == '0') {
            return 0
        }
        var res = dfs(s, i + 1)
        if (i < s.length - 1) {
            if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '7')) {
                res += dfs(s, i + 2)
            }
        }
        return res
    }
}

class Solution {
    func numDecodings(_ s: String) -> Int {
        let chars = Array(s)

        func dfs(_ i: Int) -> Int {
            if i == chars.count {
                return 1
            }
            if chars[i] == "0" {
                return 0
            }

            var res = dfs(i + 1)
            if i < chars.count - 1 {
                if chars[i] == "1" || (chars[i] == "2" && chars[i + 1] < "7") {
                    res += dfs(i + 2)
                }
            }

            return res
        }

        return dfs(0)
    }
}

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let s = s.as_bytes();

        fn dfs(s: &[u8], i: usize) -> i32 {
            if i == s.len() {
                return 1;
            }
            if s[i] == b'0' {
                return 0;
            }

            let mut res = dfs(s, i + 1);
            if i < s.len() - 1 {
                if s[i] == b'1' || (s[i] == b'2' && s[i + 1] < b'7') {
                    res += dfs(s, i + 2);
                }
            }
            res
        }

        dfs(s, 0)
    }
}

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

This is the same decoding logic as the recursive approach, but with memoization to avoid recomputing the same subproblems.

Observation:

While decoding, the same index i is reached multiple times.
The number of ways to decode s[i:] never changes, so we can store it once and reuse it.

So instead of recalculating:

“How many ways can I decode from index i?”

we cache the answer the first time we compute it.

This converts the exponential recursion into linear time.

Algorithm

Use a dictionary dp where dp[i] = number of ways to decode s[i:].
Initialize base case:
- dp[len(s)] = 1 (empty string has one valid decoding).
Define recursive function dfs(i):
- If i already in dp, return dp[i].
- If s[i] == '0', return 0 (invalid).
Compute:
- Take one digit → dfs(i + 1)
- Take two digits if valid (10-26) → dfs(i + 2)
Store result in dp[i] and return it.
Call dfs(0).

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {len(s) : 1}

        def dfs(i):
            if i in dp:
                return dp[i]
            if s[i] == "0":
                return 0

            res = dfs(i + 1)
            if i + 1 < len(s) and (
                s[i] == "1" or s[i] == "2" and
                s[i + 1] in "0123456"
            ):
                res += dfs(i + 2)
            dp[i] = res
            return res

        return dfs(0)

public class Solution {

    public int numDecodings(String s) {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(s.length(), 1);

        return dfs(s, 0, dp);
    }

    private int dfs(String s, int i, Map<Integer, Integer> dp) {
        if (dp.containsKey(i)) {
            return dp.get(i);
        }
        if (s.charAt(i) == '0') {
            return 0;
        }

        int res = dfs(s, i + 1, dp);
        if (i + 1 < s.length() && (s.charAt(i) == '1' ||
           s.charAt(i) == '2' && s.charAt(i + 1) < '7')) {
            res += dfs(s, i + 2, dp);
        }
        dp.put(i, res);
        return res;
    }
}

class Solution {
public:
    int numDecodings(string s) {
        unordered_map<int, int> dp;
        dp[s.size()] = 1;
        return dfs(s, 0, dp);
    }

private:
    int dfs(string s, int i, unordered_map<int, int>& dp) {
        if (dp.count(i)) {
            return dp[i];
        }
        if (s[i] == '0') {
            return 0;
        }

        int res = dfs(s, i + 1, dp);
        if (i + 1 < s.size() && (s[i] == '1' ||
            s[i] == '2' && s[i + 1] < '7')) {
            res += dfs(s, i + 2, dp);
        }
        dp[i] = res;
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    numDecodings(s) {
        const dp = new Map();
        dp.set(s.length, 1);

        return this.dfs(s, 0, dp);
    }

    /**
     * @param {string} s
     * @param {number} i
     * @param {Map} dp
     * @return {number}
     */
    dfs(s, i, dp) {
        if (dp.has(i)) {
            return dp.get(i);
        }
        if (s.charAt(i) === '0') {
            return 0;
        }

        let res = this.dfs(s, i + 1, dp);
        if (
            i + 1 < s.length &&
            (s.charAt(i) === '1' ||
                (s.charAt(i) === '2' && s.charAt(i + 1) < '7'))
        ) {
            res += this.dfs(s, i + 2, dp);
        }
        dp.set(i, res);
        return res;
    }
}

public class Solution {

    public int NumDecodings(string s) {
        Dictionary<int, int> dp = new Dictionary<int, int>();
        dp[s.Length] = 1;
        return Dfs(s, 0, dp);
    }

    private int Dfs(string s, int i, Dictionary<int, int> dp) {
        if (dp.ContainsKey(i)) {
            return dp[i];
        }
        if (s[i] == '0') {
            return 0;
        }

        int res = Dfs(s, i + 1, dp);
        if (i + 1 < s.Length && (s[i] == '1' ||
            s[i] == '2' && s[i + 1] < '7')) {
            res += Dfs(s, i + 2, dp);
        }
        dp[i] = res;
        return res;
    }
}

class Solution {
    fun numDecodings(s: String): Int {
        return dfs(s, 0, hashMapOf(s.length to 1))
    }

    fun dfs(s: String, i: Int, dp: HashMap<Int, Int>): Int {
        if (i in dp) {
            return dp[i]!!
        }
        if (i == s.length) {
            return 1
        }
        if (s[i] == '0') {
            return 0
        }
        var res = dfs(s, i + 1, dp)
        if (i + 1 < s.length && (s[i] == '1' ||
           (s[i] == '2' && s[i + 1] <= '6'))) {
            res += dfs(s, i + 2, dp)
        }
        dp[i] = res
        return res
    }
}

class Solution {
    func numDecodings(_ s: String) -> Int {
        let chars = Array(s)
        var dp = [Int: Int]()
        dp[chars.count] = 1

        func dfs(_ i: Int) -> Int {
            if let cached = dp[i] {
                return cached
            }
            if chars[i] == "0" {
                return 0
            }

            var res = dfs(i + 1)
            if i + 1 < chars.count,
               chars[i] == "1" || (chars[i] == "2" && "0123456".contains(chars[i + 1])) {
                res += dfs(i + 2)
            }
            dp[i] = res
            return res
        }

        return dfs(0)
    }
}

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut dp = HashMap::new();
        dp.insert(n, 1);

        fn dfs(s: &[u8], i: usize, dp: &mut HashMap<usize, i32>) -> i32 {
            if let Some(&val) = dp.get(&i) {
                return val;
            }
            if s[i] == b'0' {
                return 0;
            }

            let mut res = dfs(s, i + 1, dp);
            if i + 1 < s.len()
                && (s[i] == b'1' || (s[i] == b'2' && s[i + 1] < b'7'))
            {
                res += dfs(s, i + 2, dp);
            }
            dp.insert(i, res);
            res
        }

        dfs(s, 0, &mut dp)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

This is the iterative version of the decoding logic.

Instead of asking:

“How many ways can I decode starting at index i?”

recursively, we build the answer from the back.

Key idea:

Let dp[i] = number of ways to decode the substring s[i:]
The answer we want is dp[0]
Each position depends only on the next one or two positions → perfect for bottom-up DP

Algorithm

Create a DP table (or map) where:
- dp[i] = number of ways to decode s[i:]
Base case:
- dp[len(s)] = 1 (empty string has one valid decoding)
Iterate i from right to left:
- If s[i] == '0' → dp[i] = 0 (invalid start)
- Else:
  - Take one digit → dp[i] = dp[i + 1]
  - Take two digits if valid (10-26) → add dp[i + 2]
Return dp[0]

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {len(s): 1}
        for i in range(len(s) - 1, -1, -1):
            if s[i] == "0":
                dp[i] = 0
            else:
                dp[i] = dp[i + 1]

            if i + 1 < len(s) and (s[i] == "1" or
               s[i] == "2" and s[i + 1] in "0123456"
            ):
                dp[i] += dp[i + 2]
        return dp[0]

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    numDecodings(s) {
        let dp = new Array(s.length + 1).fill(0);
        dp[s.length] = 1;
        for (let i = s.length - 1; i >= 0; i--) {
            if (s.charAt(i) === '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (
                    i + 1 < s.length &&
                    (s.charAt(i) === '1' ||
                        (s.charAt(i) === '2' && s.charAt(i + 1) < '7'))
                ) {
                    dp[i] += dp[i + 2];
                }
            }
        }
        return dp[0];
    }
}

public class Solution {
    public int NumDecodings(string s) {
        int[] dp = new int[s.Length + 1];
        dp[s.Length] = 1;
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 < s.Length && (s[i] == '1' ||
                    s[i] == '2' && s[i + 1] < '7')) {
                    dp[i] += dp[i + 2];
                }
            }
        }
        return dp[0];
    }
}

class Solution {
    fun numDecodings(s: String): Int {
        val dp = mutableMapOf(s.length to 1)
        for (i in s.length - 1 downTo 0) {
            if (s[i] == '0') {
                dp[i] = 0
            } else {
                dp[i] = dp[i + 1] ?: 0
                if (i + 1 < s.length && (s[i] == '1' ||
                   (s[i] == '2' && s[i + 1] <= '6'))) {
                    dp[i] = dp[i]!! + (dp[i + 2] ?: 0)
                }
            }
        }
        return dp[0] ?: 0
    }
}

class Solution {
    func numDecodings(_ s: String) -> Int {
        let chars = Array(s)
        var dp = [Int: Int]()
        dp[chars.count] = 1

        for i in stride(from: chars.count - 1, through: 0, by: -1) {
            if chars[i] == "0" {
                dp[i] = 0
            } else {
                dp[i] = dp[i + 1] ?? 0
            }

            if i + 1 < chars.count,
               chars[i] == "1" || (chars[i] == "2" && "0123456".contains(chars[i + 1])) {
                dp[i]! += dp[i + 2] ?? 0
            }
        }
        return dp[0] ?? 0
    }
}

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut dp = vec![0i32; n + 1];
        dp[n] = 1;

        for i in (0..n).rev() {
            if s[i] == b'0' {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if i + 1 < n && (s[i] == b'1' || (s[i] == b'2' && s[i + 1] < b'7')) {
                    dp[i] += dp[i + 2];
                }
            }
        }
        dp[0]
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Space Optimized)

Intuition

This is the space-optimized version of bottom-up DP.

From the bottom-up approach, we know:

dp[i] depends only on dp[i+1] and dp[i+2]
So we don’t need an entire DP array

We just keep:

dp1 → ways to decode from i + 1
dp2 → ways to decode from i + 2

At each index i, we compute the current answer using these two values, then shift them forward.

Algorithm

Initialize:
- dp1 = 1 → corresponds to dp[len(s)]
- dp2 = 0
Iterate from right to left:
- If s[i] == '0' → current ways = 0
- Else:
  - Start with dp1 (take one digit)
  - If two digits form a valid number (10-26), add dp2
After computing current:
- Shift values:
  - dp2 = dp1
  - dp1 = current
Return dp1

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = dp2 = 0
        dp1 = 1
        for i in range(len(s) - 1, -1, -1):
            if s[i] == "0":
                dp = 0
            else:
                dp = dp1

            if i + 1 < len(s) and (s[i] == "1" or
               s[i] == "2" and s[i + 1] in "0123456"
            ):
                dp += dp2
            dp, dp1, dp2 = 0, dp, dp1
        return dp1

public class Solution {
    public int numDecodings(String s) {
        int dp = 0, dp2 = 0;
        int dp1 = 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                dp = 0;
            } else {
                dp = dp1;
                if (i + 1 < s.length() && (s.charAt(i) == '1' ||
                    s.charAt(i) == '2' && s.charAt(i + 1) < '7')) {
                    dp += dp2;
                }
            }
            dp2 = dp1;
            dp1 = dp;
            dp = 0;
        }
        return dp1;
    }
}

class Solution {
public:
    int numDecodings(string s) {
        int dp = 0, dp2 = 0;
        int dp1 = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp = 0;
            } else {
                dp = dp1;
                if (i + 1 < s.size() && (s[i] == '1' ||
                    s[i] == '2' && s[i + 1] < '7')) {
                    dp += dp2;
                }
            }
            dp2 = dp1;
            dp1 = dp;
            dp = 0;
        }
        return dp1;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    numDecodings(s) {
        let dp2 = 0,
            dp = 0;
        let dp1 = 1;
        for (let i = s.length - 1; i >= 0; i--) {
            if (s.charAt(i) === '0') {
                dp = 0;
            } else {
                dp = dp1;
                if (
                    i + 1 < s.length &&
                    (s.charAt(i) === '1' ||
                        (s.charAt(i) === '2' && s.charAt(i + 1) < '7'))
                ) {
                    dp += dp2;
                }
            }
            dp2 = dp1;
            dp1 = dp;
            dp = 0;
        }
        return dp1;
    }
}

public class Solution {
    public int NumDecodings(string s) {
        int dp = 0, dp1 = 1, dp2 = 0;
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp = 0;
            } else {
                dp = dp1;
                if (i + 1 < s.Length && (s[i] == '1' ||
                    s[i] == '2' && s[i + 1] < '7')) {
                    dp += dp2;
                }
            }
            dp2 = dp1;
            dp1 = dp;
            dp = 0;
        }
        return dp1;
    }
}

func numDecodings(s string) int {
    dp, dp2 := 0, 0
    dp1 := 1
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '0' {
            dp = 0
        } else {
            dp = dp1
        }
        if i+1 < len(s) && (s[i] == '1' ||
           s[i] == '2' && s[i+1] <= '6') {
            dp += dp2
        }
        dp2 = dp1
        dp1 = dp
        dp = 0
    }
    return dp1
}

class Solution {
    fun numDecodings(s: String): Int {
        var dp = 0
        var dp2 = 0
        var dp1 = 1
        for (i in s.length - 1 downTo 0) {
            if (s[i] == '0') {
                dp = 0
            } else {
                dp = dp1
            }
            if (i + 1 < s.length && (s[i] == '1' ||
               (s[i] == '2' && s[i + 1] <= '6'))) {
                dp += dp2
            }
            dp2 = dp1
            dp1 = dp
        }
        return dp1
    }
}

class Solution {
    func numDecodings(_ s: String) -> Int {
        let chars = Array(s)
        var dp = 0, dp1 = 1, dp2 = 0

        for i in stride(from: chars.count - 1, through: 0, by: -1) {
            if chars[i] == "0" {
                dp = 0
            } else {
                dp = dp1
            }

            if i + 1 < chars.count,
               chars[i] == "1" || (chars[i] == "2" && "0123456".contains(chars[i + 1])) {
                dp += dp2
            }
            (dp, dp1, dp2) = (0, dp, dp1)
        }
        return dp1
    }
}

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let s = s.as_bytes();
        let mut dp = 0i32;
        let mut dp1 = 1i32;
        let mut dp2 = 0i32;

        for i in (0..s.len()).rev() {
            if s[i] == b'0' {
                dp = 0;
            } else {
                dp = dp1;
                if i + 1 < s.len()
                    && (s[i] == b'1' || (s[i] == b'2' && s[i + 1] < b'7'))
                {
                    dp += dp2;
                }
            }
            dp2 = dp1;
            dp1 = dp;
            dp = 0;
        }
        dp1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Not Handling Leading Zeros

A string starting with '0' or containing '0' that cannot pair with the previous digit has zero valid decodings. This is the most common edge case to miss.

# Wrong: doesn't handle '0' case
res = dfs(i + 1)

# Correct: return 0 for invalid '0'
if s[i] == '0':
    return 0
res = dfs(i + 1)

Incorrect Two-Digit Validation

Two digits form a valid decoding only if they represent 10-26. Common mistakes include allowing "00", "07", or values above 26.

# Wrong: allows invalid two-digit codes like "00" or "30"
if i + 1 < len(s):
    res += dfs(i + 2)

# Correct: only allow 10-26
if i + 1 < len(s) and (s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')):
    res += dfs(i + 2)

Confusing Base Case Value

When the entire string is decoded (index reaches the end), there is exactly 1 valid decoding (the one that got us here). Returning 0 instead causes all paths to count as zero.

# Wrong: returns 0, making all counts zero
if i == len(s):
    return 0

# Correct: reaching the end means one valid decoding
if i == len(s):
    return 1