Leet Code 91. Decode Ways — Graphically Explained

Decoding Ways Using Backtracking and Dynamic Programming

In this blog post, we will discuss a problem that involves determining the number of ways a string of digits can be decoded into letters. This is a well-known problem, often referred to as the “Decode Ways” problem, where each digit or pair of digits is mapped to a letter (e.g., 1 = ‘A’, 2 = ‘B’, …, 26 = ‘Z’).

We will first approach the solution using backtracking (recursion), which gives us insight into how we can further optimize the solution with dynamic programming. The accompanying image represents a recursive tree, showing different function calls and how the problem branches.

---

Part 1: Backtracking Approach

Problem Statement:

Given a string of digits (for example, “226”), determine how many ways it can be decoded into letters. The rules are:

• Each digit from 1-9 can map to a letter (‘A’ to ‘I’).
• Each two-digit number from 10-26 can map to letters (‘J’ to ‘Z’).

Backtracking:

The simplest way to solve the problem is by using a recursive backtracking approach. The idea is to make choices at each step:

1. Decode one digit (which must be between 1 and 9).
2. Decode two digits (which must be between 10 and 26).

Each recursive call represents a decision, either taking one digit or two digits, until you reach the end of the string. If a valid decoding is reached, it’s counted as one way.

Here is the Javascript for the backtracking approach:

function decodeWays(s) {
    function backtrack(index) {
        if (index === s.length) return 1;
        if (s[index] === '0') return 0; // Invalid starting character
        
        let count = 0;
        
        // Single digit decoding
        count += backtrack(index + 1);
        
        // Two digits decoding
        if (index < s.length - 1 && (s[index] === '1' || (s[index] === '2' && s[index + 1] <= '6'))) {
            count += backtrack(index + 2);
        }
        
        return count;
    }
    
    return backtrack(0);
}

In this approach:

• We recursively explore both options (one digit or two digits) at each step.

• The base case is when the index reaches the end of the string, meaning we have successfully decoded it.
  
  The image represents the recursive tree structure for the backtracking approach. Each node in the tree represents a call to the function decodeWays(n, index):

• Root Node: The root represents the original string “226”.

• Branches: Each node branches into two paths:

  1. Taking one digit and making a recursive call for the remaining string.
  2. Taking two digits (if valid) and making a recursive call for the remaining string.

The arrows in the tree show the flow of recursion, while the return values are shown as numbers on the edges (e.g., 1, 2, etc.). The image highlights how the same subproblems are recomputed, which motivates us to optimize the approach using dynamic programming.

Analysis of Backtracking:

Backtracking is simple but highly inefficient, as it generates many overlapping subproblems. The tree shown in the image demonstrates how different paths (like decodeWays(226, 1) and decodeWays(226, 2)) are repeatedly computed, leading to exponential time complexity, specifically $O(2n)O(2^n)O(2n)$ for a string of length nnn.

---

Part 2: Optimization with Dynamic Programming

Dynamic Programming (DP) Approach:

To optimize the backtracking approach, we observe that the same subproblems are being solved multiple times. For example, the recursive calls decodeWays(226, 1) and decodeWays(226, 2) are made multiple times with the same arguments. Dynamic programming helps in avoiding this redundancy by storing the results of already solved subproblems.

We can implement a bottom-up dynamic programming solution, where we store the number of ways to decode the string from index iii to the end. The idea is to build the solution starting from the end of the string and moving backward.

Here’s how we can approach it:

1. Define a DP array where dp[i] represents the number of ways to decode the substring starting at index iii.
2. Initialize: dp[n] = 1 (there is exactly one way to decode an empty string).
3. For each index iii from n−1n-1n−1 to 0:
   • If the digit at iii is ‘0’, set dp[i] = 0 (no valid decoding).
   • Otherwise, set dp[i] = dp[i+1] (decoding the single digit).
   • If the two-digit number formed by s[i]s[i]s[i] and s[i+1]s[i+1]s[i+1] is between 10 and 26, add dp[i+2] to dp[i].

Here’s the dynamic programming code:

function decodeWaysDP(s) {
    if (!s || s[0] === '0') return 0;
    
    const n = s.length;
    const dp = Array(n + 1).fill(0);
    dp[0] = 1; // Base case: An empty string has one way to be decoded
    dp[1] = s[0] !== '0' ? 1 : 0; // Base case: Single character string
    
    for (let i = 2; i <= n; i++) {
        const oneDigit = s.substring(i - 1, i);
        const twoDigits = s.substring(i - 2, i);
        
        // Check one-digit decode
        if (oneDigit >= '1' && oneDigit <= '9') {
            dp[i] += dp[i - 1];
        }
        
        // Check two-digit decode
        if (twoDigits >= '10' && twoDigits <= '26') {
            dp[i] += dp[i - 2];
        }
    }
    
    return dp[n];
}

Time and Space Complexity:

• Time Complexity:$O(n)O(n)O(n)$, where nnn is the length of the string. We only process each character once.
• Space Complexity: $O(n)O(n)O(n)$ because of the DP array. However, we can further optimize the space to $O(1)O(1)O(1)$ by only keeping track of the last two states.

Memoization (Top-Down) Approach:

If you prefer a recursive solution but want the efficiency of dynamic programming, you can use memoization. Here, instead of solving each subproblem multiple times, we store the results of the subproblems in a cache, avoiding redundant calculations.

---

Conclusion

Backtracking provides an intuitive way to solve the problem but leads to redundant calculations and inefficiency. By leveraging dynamic programming, we can optimize the solution to run in linear time. Understanding the recursive tree helps in visualizing the problem’s structure, making it easier to comprehend how dynamic programming improves performance.