Decode Ways

Med

#0091Time: O(2^n)Space: O(n)21 companies

Patterns

Dynamic Programming

Data structures

String

Companies

Adobe Amazon Apple Bloomberg

Prompt

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).

Approaches

4 approaches with complexity analysis and trade-offs.

This approach directly translates the problem's logic into a recursive function. For any given position in the string, we explore two possibilities: decoding a single digit or decoding two digits. The total number of ways is the sum of the ways from these two paths. This process continues until we reach the end of the string or encounter an invalid sequence.

Algorithm

Define a recursive function solve(index) that returns the number of ways to decode the substring s.substring(index).
Base Case 1: If index is equal to the length of the string s, it means we have successfully found a valid decoding for the entire string. Return 1.
Base Case 2: If the character at s.charAt(index) is '0', it's an invalid starting point for a code. Return 0.
Recursive Step:
- Initialize ways by considering a single-digit decoding. This corresponds to the number of ways to decode the rest of the string, so we make a recursive call solve(index + 1).
- Check if a two-digit decoding is possible. This is true if index is not the second to last character and the number formed by s.substring(index, index + 2) is between 10 and 26.
- If a two-digit decoding is valid, add the number of ways for that path to our ways count by making a recursive call solve(index + 2).
Return the total ways.
The initial call to start the process is solve(0).

Walkthrough

The core idea is to define a function that solves the problem for a suffix of the original string. Let's say solve(index) calculates the number of ways to decode s[index:].

If we are at index, we can try to decode s[index] as a single digit. If it's a valid digit (1-9), the number of ways is equal to the number of ways we can decode the rest of the string, which is solve(index + 1).
We can also try to decode s[index:index+2] as a two-digit number. If it's a valid number (10-26), we add the number of ways we can decode the rest of the string, solve(index + 2), to our total.

The base cases for the recursion are when we reach the end of the string (a successful decoding) or when we encounter an invalid character like '0' at the start of a code.

1class Solution {2    public int numDecodings(String s) {3        return solve(0, s);4    }5 6    private int solve(int index, String s) {7        // Base case: If we've reached the end, we found one valid decoding.8        if (index == s.length()) {9            return 1;10        }11 12        // If the current digit is '0', it cannot be decoded on its own.13        if (s.charAt(index) == '0') {14            return 0;15        }16 17        // Case 1: Decode a single digit.18        int ways = solve(index + 1, s);19 20        // Case 2: Decode two digits, if possible.21        if (index + 1 < s.length()) {22            int twoDigit = Integer.parseInt(s.substring(index, index + 2));23            if (twoDigit >= 10 && twoDigit <= 26) {24                ways += solve(index + 2, s);25            }26        }27 28        return ways;29    }30}

Complexity

Time

O(2^n)

Space

O(n)

Trade-offs

Pros

Simple to understand and implement as it directly models the problem statement.
The code is clean and follows a natural, top-down thought process.

Cons

Extremely inefficient due to a large number of redundant computations. The function recalculates the number of ways for the same substring multiple times.
Will likely result in a 'Time Limit Exceeded' (TLE) error for input strings with a length greater than ~35-40.

This approach, also known as top-down dynamic programming, optimizes the brute-force recursion. It recognizes that the recursive solution repeatedly solves the same subproblems (e.g., calculating the number of ways to decode the same suffix of the string). By storing the result of each subproblem in a memoization table the first time it's computed, we can simply look up the result in constant time for all subsequent calls, avoiding redundant work.

Algorithm

Create a memoization array, memo, of size s.length() + 1, and initialize it with a sentinel value (e.g., -1) to indicate that a subproblem's result has not been computed.
Use the same recursive function solve(index) as in the brute-force approach.
Memoization Check: At the beginning of the solve(index) function, check if memo[index] has been computed. If memo[index] is not -1, return the stored value immediately.
Store Result: After computing the number of ways for a given index, store this result in memo[index] before returning it.
The rest of the recursive logic (base cases, single-digit, and two-digit decoding) remains the same.

Walkthrough

We enhance the previous recursive solution by adding a cache, typically an array, to store the results of solve(index). This technique is called memoization.

Before diving into the recursive calculation for an index i, we first check if we have already solved for this index. If we have, we return the cached result. If not, we perform the calculation as before. Once the result is found, we store it in our cache before returning. This ensures that each subproblem solve(i) is computed only once.

1class Solution {2    public int numDecodings(String s) {3        int[] memo = new int[s.length() + 1];4        java.util.Arrays.fill(memo, -1);5        return solve(0, s, memo);6    }7 8    private int solve(int index, String s, int[] memo) {9        // Base case: If we've reached the end, we found one valid decoding.10        if (index == s.length()) {11            return 1;12        }13 14        // If result for this index is already computed, return it.15        if (memo[index] != -1) {16            return memo[index];17        }18 19        // If the current digit is '0', it cannot be decoded.20        if (s.charAt(index) == '0') {21            memo[index] = 0;22            return 0;23        }24 25        // Case 1: Decode a single digit.26        int ways = solve(index + 1, s, memo);27 28        // Case 2: Decode two digits, if possible.29        if (index + 1 < s.length()) {30            int twoDigit = Integer.parseInt(s.substring(index, index + 2));31            if (twoDigit >= 10 && twoDigit <= 26) {32                ways += solve(index + 2, s, memo);33            }34        }35 36        // Store the result and return.37        memo[index] = ways;38        return ways;39    }40}

Complexity

Time

O(n)

Space

O(n)

Trade-offs

Pros

Drastically improves time complexity from exponential to linear.
Guaranteed to pass within the time limits for the given constraints.
Maintains the intuitive, top-down structure of the recursive solution.

Cons

Uses O(n) space for the memoization array.
Still uses recursion, which has some overhead compared to an iterative solution and could theoretically lead to a stack overflow on extremely large inputs (though not an issue with the given constraints).

This approach, also known as bottom-up dynamic programming, solves the problem iteratively. We build the solution from smaller subproblems to larger ones. We use an array, dp, where dp[i] represents the number of ways to decode the prefix of the string of length i. The value of dp[i] is calculated based on the previously computed values dp[i-1] and dp[i-2], effectively building the solution from left to right.

Algorithm

Create a DP array, dp, of size n + 1, where n is the length of the string s.
dp[i] will store the number of ways to decode the prefix of the string of length i (i.e., s.substring(0, i)).
Initialization:
- dp[0] = 1 (There is one way to decode an empty string).
- dp[1] = s.charAt(0) == '0' ? 0 : 1.
Iteration: Loop from i = 2 to n.
- For each i, calculate dp[i] based on the last one or two characters of the substring s.substring(0, i).
- One-digit case: Check the last digit s.charAt(i-1). If it's not '0', it can be decoded by itself. So, we add the number of ways to decode s.substring(0, i-1), which is dp[i-1], to dp[i].
- Two-digit case: Check the last two digits s.substring(i-2, i). If they form a number between 10 and 26, they can be decoded together. So, we add the number of ways to decode s.substring(0, i-2), which is dp[i-2], to dp[i].
The final answer is dp[n].

Walkthrough

Instead of a top-down recursive approach, we can solve this problem from the bottom up. We can define dp[i] as the number of ways to decode the string prefix of length i. Our goal is to find dp[n], where n is the total length of the string.

The recurrence relation is as follows: dp[i] = (ways from decoding s[i-1]) + (ways from decoding s[i-2:i])

If s[i-1] is a valid single digit (1-9), it contributes dp[i-1] ways.
If s[i-2:i] is a valid two-digit number (10-26), it contributes dp[i-2] ways.

We can build this dp table starting from the base cases dp[0] and dp[1] and iterating up to dp[n].

1class Solution {2    public int numDecodings(String s) {3        if (s == null || s.length() == 0) {4            return 0;5        }6        int n = s.length();7        int[] dp = new int[n + 1];8        9        // dp[i] = number of ways to decode s.substring(0, i)10        dp[0] = 1; // Base case: one way to decode an empty string11        12        // If the first character is '0', it's impossible to decode.13        // Otherwise, there's one way to decode the first character.14        dp[1] = s.charAt(0) == '0' ? 0 : 1;15 16        for (int i = 2; i <= n; i++) {17            // Check for one-digit decoding18            int oneDigit = Integer.parseInt(s.substring(i - 1, i));19            if (oneDigit >= 1 && oneDigit <= 9) {20                dp[i] += dp[i - 1];21            }22 23            // Check for two-digit decoding24            int twoDigit = Integer.parseInt(s.substring(i - 2, i));25            if (twoDigit >= 10 && twoDigit <= 26) {26                dp[i] += dp[i - 2];27            }28        }29        30        return dp[n];31    }32}

Complexity

Time

O(n)

Space

O(n)

Trade-offs

Pros

Very efficient with a linear time complexity.
Avoids recursion, eliminating recursion overhead and the risk of stack overflow.
The bottom-up approach can be more intuitive for some problems.

Cons

Uses O(n) extra space for the DP array, which is not optimal.

This is the most optimized solution. It builds upon the iterative DP approach by recognizing that we don't need to store the entire DP table. Since the number of ways to decode up to position i only depends on the results for i-1 and i-2, we can discard older results. By using just two variables to keep track of the last two computed values, we can achieve the same linear time complexity while reducing the space complexity to constant.

Algorithm

Observe that the calculation of dp[i] only depends on the two preceding values, dp[i-1] and dp[i-2].
Instead of a full DP array, we can use just two variables to store these values. Let's call them prev1 (for dp[i-1]) and prev2 (for dp[i-2]).
Initialization:
- Handle edge cases like an empty string or a string starting with '0'.
- prev2 = 1 (representing dp[0])
- prev1 = 1 (representing dp[1], assuming the first character is valid).
Iteration: Loop from i = 2 to n.
- In each iteration, calculate a current value which would be dp[i].
- current is calculated using prev1 and prev2 with the same logic as the DP approach (checking one-digit and two-digit decodings).
- After calculating current, update the variables for the next iteration: prev2 becomes the old prev1, and prev1 becomes current.
The final answer is prev1 after the loop completes.

Walkthrough

We can optimize the space complexity of the iterative DP solution. Notice that to compute dp[i], we only need access to dp[i-1] and dp[i-2]. This pattern is similar to calculating Fibonacci numbers, where the current number is the sum of the previous two. We don't need to store the entire array of previous results.

We can use two variables to keep track of the last two values. Let's say prev2 holds the value for dp[i-2] and prev1 holds the value for dp[i-1]. We can then calculate the current value (for dp[i]) and update prev2 and prev1 for the next iteration. This reduces the space requirement from O(n) to O(1).

1class Solution {2    public int numDecodings(String s) {3        if (s == null || s.length() == 0 || s.charAt(0) == '0') {4            return 0;5        }6        int n = s.length();7        if (n == 1) {8            return 1;9        }10 11        // prev2 represents dp[i-2], prev1 represents dp[i-1]12        int prev2 = 1; // Corresponds to dp[0]13        int prev1 = 1; // Corresponds to dp[1]14 15        for (int i = 2; i <= n; i++) {16            int current = 0;17            18            // Check for one-digit decoding19            int oneDigit = s.charAt(i - 1) - '0';20            if (oneDigit >= 1) {21                current += prev1;22            }23 24            // Check for two-digit decoding25            int twoDigit = Integer.parseInt(s.substring(i - 2, i));26            if (twoDigit >= 10 && twoDigit <= 26) {27                current += prev2;28            }29            30            prev2 = prev1;31            prev1 = current;32        }33        34        return prev1;35    }36}

Complexity

Time

O(n)

Space

O(1)

Trade-offs

Pros

Optimal solution with linear time and constant space complexity.
Extremely efficient for the given constraints.

Cons

The logic of updating the state variables (prev1, prev2) can be slightly more complex to reason about than using a full DP array.

Solutions

Solution

1public class Solution { public int NumDecodings ( string s ) { int n = s . Length ; int f = 0 , g = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { int h = s [ i - 1 ] != '0' ? g : 0 ; if ( i > 1 && ( s [ i - 2 ] == '1' || ( s [ i - 2 ] == '2' && s [ i - 1 ] <= '6' ))) { h += f ; } f = g ; g = h ; } return g ; } }

1class Solution {2public3  int numDecodings(String s) {4    int n = s.length();5    int f = 0, g = 1;6    for (int i = 1; i <= n; ++i) {7      int h = s.charAt(i - 1) != '0' ? g : 0;8      if (i > 1 && s.charAt(i - 2) != '0' &&9          Integer.valueOf(s.substring(i - 2, i)) <= 26) {10        h += f;11      }12      f = g;13      g = h;14    }15    return g;16  }17}

1class Solution {2public:3  int numDecodings(string s) {4    int n = s.size();5    int f = 0, g = 1;6    for (int i = 1; i <= n; ++i) {7      int h = s[i - 1] != '0' ? g : 0;8      if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {9        h += f;10      }11      f = g;12      g = h;13    }14    return g;15  }16};

1''' >>> s = "abcdef" >>> [(i,c) for i, c in enumerate(s, 1)] [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e'), (6, 'f')] ''' class Solution : def numDecodings ( self , s : str ) -> int : # f: i-2 # g: i-1 f , g = 0 , 1 for i , c in enumerate ( s , 1 ): h = g if c != "0" else 0 if i > 1 and s [ i - 2 ] != "0" and int ( s [ i - 2 : i ]) <= 26 : h += f f , g = g , h return g ############## class Solution : def numDecodings ( self , s : str ) -> int : if len ( s ) == 0 : return 0 length = len ( s ) dp = [ 0 ] * ( length + 1 ) # dp[i] => at index i, its decode ways dp [ length ] = 1 # initiator, just make forloop flow working dp [ length - 1 ] = 0 if s [ length - 1 ] == '0' else 1 # assumption is starting at i, so starting as 0 is not decodable # start at 'len-2' # or else below 'dp[i+2]' will out of index boundary for i in range ( length - 2 , - 1 , - 1 ): if s [ i ] == '0' : continue tem = int ( s [ i : i + 2 ]) if tem > 26 : dp [ i ] = dp [ i + 1 ] else : dp [ i ] = dp [ i + 1 ] + dp [ i + 2 ] return dp [ 0 ] # optimized from above solution, no dp array class Solution : def numDecodings ( self , s : str ) -> int : n = len ( s ) # a: dp[i-2], b: dp[i-1], c: count for current index i a , b , c = 0 , 1 , 0 for i in range ( 1 , n + 1 ): c = 0 if s [ i - 1 ] != '0' : c += b if i > 1 and s [ i - 2 ] != '0' and ( int ( s [ i - 2 ]) * 10 + int ( s [ i - 1 ]) <= 26 ): c += a a , b = b , c return c ############## class Solution : def numDecodings ( self , s : str ) -> int : n = len ( s ) dp = [ 0 ] * ( n + 1 ) dp [ 0 ] = 1 for i in range ( 1 , n + 1 ): if s [ i - 1 ] != '0' : dp [ i ] += dp [ i - 1 ] if i > 1 and s [ i - 2 ] != '0' and ( int ( s [ i - 2 ]) * 10 + int ( s [ i - 1 ]) <= 26 ): dp [ i ] += dp [ i - 2 ] return dp [ n ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution { public int NumDecodings ( string s ) { int n = s . Length ; int f = 0 , g = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { int h = s [ i - 1 ] != '0' ? g : 0 ; if ( i > 1 && ( s [ i - 2 ] == '1' || ( s [ i - 2 ] == '2' && s [ i - 1 ] <= '6' ))) { h += f ; } f = g ; g = h ; } return g ; } }

1class Solution {2public3  int numDecodings(String s) {4    int n = s.length();5    int f = 0, g = 1;6    for (int i = 1; i <= n; ++i) {7      int h = s.charAt(i - 1) != '0' ? g : 0;8      if (i > 1 && s.charAt(i - 2) != '0' &&9          Integer.valueOf(s.substring(i - 2, i)) <= 26) {10        h += f;11      }12      f = g;13      g = h;14    }15    return g;16  }17}

1class Solution {2public:3  int numDecodings(string s) {4    int n = s.size();5    int f = 0, g = 1;6    for (int i = 1; i <= n; ++i) {7      int h = s[i - 1] != '0' ? g : 0;8      if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {9        h += f;10      }11      f = g;12      g = h;13    }14    return g;15  }16};

1''' >>> s = "abcdef" >>> [(i,c) for i, c in enumerate(s, 1)] [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e'), (6, 'f')] ''' class Solution : def numDecodings ( self , s : str ) -> int : # f: i-2 # g: i-1 f , g = 0 , 1 for i , c in enumerate ( s , 1 ): h = g if c != "0" else 0 if i > 1 and s [ i - 2 ] != "0" and int ( s [ i - 2 : i ]) <= 26 : h += f f , g = g , h return g ############## class Solution : def numDecodings ( self , s : str ) -> int : if len ( s ) == 0 : return 0 length = len ( s ) dp = [ 0 ] * ( length + 1 ) # dp[i] => at index i, its decode ways dp [ length ] = 1 # initiator, just make forloop flow working dp [ length - 1 ] = 0 if s [ length - 1 ] == '0' else 1 # assumption is starting at i, so starting as 0 is not decodable # start at 'len-2' # or else below 'dp[i+2]' will out of index boundary for i in range ( length - 2 , - 1 , - 1 ): if s [ i ] == '0' : continue tem = int ( s [ i : i + 2 ]) if tem > 26 : dp [ i ] = dp [ i + 1 ] else : dp [ i ] = dp [ i + 1 ] + dp [ i + 2 ] return dp [ 0 ] # optimized from above solution, no dp array class Solution : def numDecodings ( self , s : str ) -> int : n = len ( s ) # a: dp[i-2], b: dp[i-1], c: count for current index i a , b , c = 0 , 1 , 0 for i in range ( 1 , n + 1 ): c = 0 if s [ i - 1 ] != '0' : c += b if i > 1 and s [ i - 2 ] != '0' and ( int ( s [ i - 2 ]) * 10 + int ( s [ i - 1 ]) <= 26 ): c += a a , b = b , c return c ############## class Solution : def numDecodings ( self , s : str ) -> int : n = len ( s ) dp = [ 0 ] * ( n + 1 ) dp [ 0 ] = 1 for i in range ( 1 , n + 1 ): if s [ i - 1 ] != '0' : dp [ i ] += dp [ i - 1 ] if i > 1 and s [ i - 2 ] != '0' and ( int ( s [ i - 2 ]) * 10 + int ( s [ i - 1 ]) <= 26 ): dp [ i ] += dp [ i - 2 ] return dp [ n ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.