Exploring Backtracking and Memoization for Decoding Digit Strings

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.

Problem Breakdown

The task is to count the number of ways to decode a string of digits into letters using the mapping:

• "1" → 'A'
• "2" → 'B'
• ...
• "26" → 'Z'

Key Constraints:

A single digit (1-9) can be decoded into a letter.

1. Two digits (10-26) can also be decoded into a letter.
2. Leading zeros (e.g., "06") are invalid.

Example:

• "11106" can be decoded as:
• (1, 1, 10, 6) → "AAJF"
• (11, 10, 6) → "KJF"
• (1, 11, 06) → Invalid (because "06" is not a valid code).

Recursive Approach with Memoization

The provided solution uses recursion with memoization to efficiently count the number of valid decodings. Here's how it works:

Key Steps:

Base Cases:

• If the current index i reaches the end of the string (i === s.length), it means we've successfully decoded the entire string, so we return 1.
• If the current character is '0', it cannot be decoded alone, so we return 0.

Recursive Cases:

• Single Digit: If the current character is not '0', we recursively decode the substring starting from the next index (i + 1).
• Two Digits: If the current two characters form a valid number (between 10 and 26), we recursively decode the substring starting from the index after the next (i + 2).

Memoization:

• We use a memo map to store the results of subproblems (i.e., the number of ways to decode the substring starting at index i).
• This avoids redundant calculations and significantly improves efficiency.

function numDecodings(s) {
 // Edge case: If the string is empty or starts with '0', return 0
 if (s.length === 0 || s[0] === '0') return 0;

 // Memoization map to store results of subproblems
 const memo = new Map();

 // Start the recursive helper function from index 0
 return helper(0);

function helper(i) {
Base case: If we've reached the end of the string, return 1
 
If the current character is '0', it cannot be decoded alone
If the result for this index is already computed, return it
 
Start with the result from decoding the current character as a single digit
let result = helper(i + 1);

If the current two characters form a valid number (10-26), add the result from decoding them
   
Store the result in the memoization map

Return the result
 }

helper(0): // Starting with "123"
   // First takes just "1" and moves to position 1
  result = helper(1)
   

  helper(1): // Now looking at "23"
  // First takes just "2" and moves to position 2
  result = helper(2)   

    helper(2): // Now looking at "3"
      result = helper(3) // Takes "3"
       
      helper(3): // Reached end
        return 1 // Base case: successfully reached end
       
      // Back to helper(2)
      result = 1 // From taking "3"
      return 1

    // Back to helper(1)
    result = 1 // From taking single digit "2"
    // Now tries two digits "23"
    result += helper(3) // Adds path from taking "23"
    return 2

  // Back to helper(0)
  result = 2 // From processing after taking "1"
  // Now tries two digits "12"
  result += helper(2) // Adds path from taking "12"
  return 3

Top-down with memoization

function numDecodings(s) {
  if (s.length === 0 || s[0] === '0') return 0;
  const memo = new Map();
  return helper(0);
   
  function helper(i) {
    if (i === s.length) return 1;
    if (s[i] === '0') return 0;
    if (memo.has(i)) return memo.get(i);
     
    let result = helper(i + 1); // Take one
    if (i + 1 < s.length 
      && parseInt(s.substring(i, i + 2)) <= 26) {
       result += helper(i + 2); // Take two
    }
    memo.set(i, result);
    return result;
  }
}

Example Walkthrough (Flow for "123")

1. Initial Call: helper(0):
2. Current character: '1' (valid single digit).
3. Recursively call helper(1).
4. Second Call: helper(1):
5. Current character: '2' (valid single digit).
6. Recursively call helper(2).
7. Third Call: helper(2):
8. Current character: '3' (valid single digit).
9. Recursively call helper(3).
10. Base Case: helper(3):
11. Reached the end of the string, return 1.
12. Back to helper(2):
13. Result from helper(3) is 1.
14. Check two digits: s.substring(2, 4) is out of bounds, so skip.
15. Return 1.
16. Back to helper(1):
17. Result from helper(2) is 1.
18. Check two digits: s.substring(1, 3) → '23' (valid).
19. Recursively call helper(3) (already computed as 1).
20. Total result: 1 + 1 = 2.
21. Return 2.
22. Back to helper(0):
23. Result from helper(1) is 2.
24. Check two digits: s.substring(0, 2) → '12' (valid).
25. Recursively call helper(2) (already computed as 1).
26. Total result: 2 + 1 = 3.
27. Return 3.

another way to solve using iterative approach:

numDecodings(s) {
    if (s.length === 0 || s[0] === '0') {
        return 0;
    }

    const n = s.length;
    const dp = new Array(n + 1).fill(0);
// Empty string can be decoded in one way
    dp[0] = 1; 
// First character can be decoded in one way if it's not '0'
    dp[1] = 1;

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

        if (oneDigit >= 1 && oneDigit <= 9) {
            dp[i] += dp[i - 1];
        }

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

    return dp[n];
}

#decoding #decode #leetcode #dynamicProgramming