# Decode Ways
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/decode-ways)
Canonical: https://scaleengineer.com/dsa/problems/decode-ways
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Zoho](https://scaleengineer.com/companies/zoho), [Commvault](https://scaleengineer.com/companies/commvault), [Lyft](https://scaleengineer.com/companies/lyft), [Salesforce](https://scaleengineer.com/companies/salesforce), [Snap](https://scaleengineer.com/companies/snap), [Graviton](https://scaleengineer.com/companies/graviton), [Moengage](https://scaleengineer.com/companies/moengage)
---
## 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).

# Approaches
## Brute-Force Recursion
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.
**Time:** O(2^n) · **Space:** O(n)
**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.
### Explanation
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.

```java
class Solution {
    public int numDecodings(String s) {
        return solve(0, s);
    }

    private int solve(int index, String s) {
        // Base case: If we've reached the end, we found one valid decoding.
        if (index == s.length()) {
            return 1;
        }

        // If the current digit is '0', it cannot be decoded on its own.
        if (s.charAt(index) == '0') {
            return 0;
        }

        // Case 1: Decode a single digit.
        int ways = solve(index + 1, s);

        // Case 2: Decode two digits, if possible.
        if (index + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += solve(index + 2, s);
            }
        }

        return ways;
    }
}
```
### 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)`.

## Recursion with Memoization
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.
**Time:** O(n) · **Space:** O(n)
**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).
### Explanation
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.

```java
class Solution {
    public int numDecodings(String s) {
        int[] memo = new int[s.length() + 1];
        java.util.Arrays.fill(memo, -1);
        return solve(0, s, memo);
    }

    private int solve(int index, String s, int[] memo) {
        // Base case: If we've reached the end, we found one valid decoding.
        if (index == s.length()) {
            return 1;
        }

        // If result for this index is already computed, return it.
        if (memo[index] != -1) {
            return memo[index];
        }

        // If the current digit is '0', it cannot be decoded.
        if (s.charAt(index) == '0') {
            memo[index] = 0;
            return 0;
        }

        // Case 1: Decode a single digit.
        int ways = solve(index + 1, s, memo);

        // Case 2: Decode two digits, if possible.
        if (index + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += solve(index + 2, s, memo);
            }
        }

        // Store the result and return.
        memo[index] = ways;
        return ways;
    }
}
```
### 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.

## Iterative Dynamic Programming
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.
**Time:** O(n) · **Space:** O(n)
**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.
### Explanation
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]`.

```java
class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        
        // dp[i] = number of ways to decode s.substring(0, i)
        dp[0] = 1; // Base case: one way to decode an empty string
        
        // If the first character is '0', it's impossible to decode.
        // Otherwise, there's one way to decode the first character.
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        for (int i = 2; i <= n; i++) {
            // Check for one-digit decoding
            int oneDigit = Integer.parseInt(s.substring(i - 1, i));
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i - 1];
            }

            // Check for two-digit decoding
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n];
    }
}
```
### 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]`.

## Space-Optimized Iterative Dynamic Programming
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.
**Time:** O(n) · **Space:** O(1)
**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.
### Explanation
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).

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

        // prev2 represents dp[i-2], prev1 represents dp[i-1]
        int prev2 = 1; // Corresponds to dp[0]
        int prev1 = 1; // Corresponds to dp[1]

        for (int i = 2; i <= n; i++) {
            int current = 0;
            
            // Check for one-digit decoding
            int oneDigit = s.charAt(i - 1) - '0';
            if (oneDigit >= 1) {
                current += prev1;
            }

            // Check for two-digit decoding
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                current += prev2;
            }
            
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}
```
### 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.

# Solutions
### CSharp

```csharp
public 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 ; } }
```

### Java

```java
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.charAt(i - 1) != '0' ? g : 0;
      if (i > 1 && s.charAt(i - 2) != '0' &&
          Integer.valueOf(s.substring(i - 2, i)) <= 26) {
        h += f;
      }
      f = g;
      g = h;
    }
    return g;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numDecodings(string s) {
    int n = s.size();
    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;
  }
};

```

### Python

```python
''' >>> 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 ]
```