Letter Combinations of a Phone Number

Explain the Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

2 -> "abc"
3 -> "def"
4 -> "ghi"
5 -> "jkl"
6 -> "mno"
7 -> "pqrs"
8 -> "tuv"
9 -> "wxyz"

Example:

Input: digits = "23"

Output:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

---

Short, Easy-to-Remember Solution/Approach

To solve this problem, we can use a recursive backtracking approach:

1. Recursive Function: We'll create a helper function that builds combinations by appending letters corresponding to each digit.

2. Backtracking: If the current combination reaches the length of the input digits, we add it to the result list.

Solution in JavaScript with Code Commenting

Here's the JavaScript solution with detailed comments:

function letterCombinations(digits) {
  if (digits.length === 0) return [];

  const phoneMap = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz'
  };

  const result = [];

  // Helper function for backtracking
  function backtrack(index, path) {
    // If the current combination has reached the length of the digits, add it to the result
    if (index === digits.length) {
      result.push(path.join(''));
      return;
    }

    // Get the letters corresponding to the current digit
    const letters = phoneMap[digits[index]];

    // Loop through the letters and recurse
    for (let letter of letters) {
      path.push(letter);
      backtrack(index + 1, path);
      path.pop();
    }
  }

  // Start the backtracking with an empty path
  backtrack(0, []);

  return result;
}

Explanation of the Solution in Simple Terms

Imagine you have a phone with number buttons, and each button maps to a few letters. You want to find all the possible words you can form by pressing the buttons in a given sequence.

• Recursive Function: This is like a helper that tries to form words by adding letters corresponding to each button press.

• Backtracking: This means if the current sequence of letters reaches the length of the input digits, you add it to your list of possible words.

For each digit in the input string, you get the corresponding letters and try adding each one to your current combination. If you form a valid combination (same length as the input digits), you save it. If not, you undo your last step and try another letter.

Code Explanation in Pointers

1. Base Case Check: If the input digits string is empty, return an empty array.

2. Phone Map: Create a mapping of digits to corresponding letters.

3. Initialize Result Array: Create an empty array to store all letter combinations.

4. Define Backtracking Function: Create a recursive function to explore different combinations.

5. Base Case - Combination Formed: If the current combination's length matches the input digits, add it to the result.

6. Get Letters: Get the letters corresponding to the current digit.

7. Loop Through Letters: Try adding each letter to the current combination.

8. Recursive Call: Call the function recursively with the updated combination.

9. Backtrack: Remove the last letter from the combination before trying the next one.

10. Start Search: Start the search with an empty combination.

Complexity Analysis

• Time Complexity: O(3^N * 4^M), where N is the number of digits corresponding to 3 letters and M is the number of digits corresponding to 4 letters. This is because we generate all possible combinations.

• Space Complexity: O(3^N * 4^M), due to the result array storing all combinations and the recursion stack.

---