Problem Statement

Given a string digits containing digits from 2-9, return an array of strings containing all possible letter combinations that the number could represent. You may return the answer in any order.

The mapping of digits to letters (just like on the telephone buttons) is as given below.

• 1 -> It doesn't map any number.
• 2 -> "abc"
• 3 -> "def"
• 4 -> "ghi"
• 5 -> "jkl"
• 6 -> "mno"
• 7 -> "pqrs"
• 8 -> "tuv"
• 9 -> "wxyz"

Examples

• Example 1:

  • Input: digits = "47"
  • Expected Output: ["gp", "gq", "gr", "gs", "hp", "hq", "hr", "hs", "ip", "iq", "ir", "is"]
  • Justification: The digit '4' maps to "ghi", and '7' maps to "pqrs". Combining these letters in every possible way gives us the expected output.

• Example 2:

  • Input: digits = "29"
  • Expected Output: ["aw", "ax", "ay", "az", "bw", "bx", "by", "bz", "cw", "cx", "cy", "cz"]
  • Justification: The digit '2' maps to "abc", and '9' maps to "wxyz". The combinations of these letters result in the expected output.

• Example 3:

  • Input: digits = "7"
  • Expected Output: ["p", "q", "r", "s"]
  • Justification: The digit '7' maps to "pqrs". All possible combinations of these letters are reflected in the expected output.

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Solution

To solve this problem, we'll employ a recursive backtracking approach that efficiently explores all possible combinations of letters. This method works by starting with an empty string and adding letters corresponding to the first digit, then recursively doing the same for the next digits until all digits have been processed.

This strategy is effective because it systematically covers all combinations without repeating, ensuring we explore the entire solution space. It's akin to a depth-first search in a tree where each node represents a letter and each path from the root to a leaf forms a valid combination. By using recursion, we can simplify the code structure and directly reflect the logical flow of the solution, making the approach both intuitive and efficient for this type of combinatorial problem.

Step-by-Step Algorithm

1. Initialize a Mapping: Create a map that associates each digit with its corresponding letters, similar to a telephone keypad.

2. Check for Empty Input: If the input digit string is empty, return an empty list as there are no combinations possible.

3. Start Recursion: Call a recursive helper function (backtrack) with four parameters: an empty string to build combinations, the input digit string, the current index set to 0, and an initially empty list to store the final combinations.

4. Recursive Function - backtrack:

   • Base Case: If the current index equals the length of the digit string, it means we've constructed a full-length combination. Add the current combination string to the result list and return to explore other possibilities.
   • Iterate Through Letters: For the current digit, retrieve the corresponding letters from the map. Iterate through each letter:
     • Add the letter to the current combination string.
     • Recursively call backtrack with the updated combination string, the same digit string, the next index (current index + 1), and the result list.
     • After the recursive call returns, remove the last letter from the combination string (backtracking) to explore other letter choices for the current digit.

5. Return Result: After exploring all combinations, return the result list containing all possible letter combinations.

Algorithm Walkthrough

Let's consider the Input: digits = "47"

1. Initial Setup: The problem starts with an input string "47" and a mapping of digits to letters as per a telephone keypad. The goal is to find all possible letter combinations that the number could represent.

2. Check for Empty Input: Since "47" is not an empty string, we proceed with the algorithm.

3. Invoke Recursive Function: The backtrack function is called with the initial combination as an empty string, the input digits "47", the starting index of 0, and an empty list to store the results.

4. Recursive Function Execution - backtrack:

   • At index 0 (first digit is '4'):
     • The map returns "ghi" for '4'.
     • For each letter in "ghi" (starting with 'g'):
       • Add 'g' to the current combination and proceed to the next digit by increasing the index.
       • Now at index 1 (second digit is '7'):
         • The map returns "pqrs" for '7'.
         • For each letter in "pqrs" (starting with 'p'):
           • Add 'p' to the current combination ("g" from the previous step). The combination now is "gp".
           • Since all digits are processed (index would move to 2, which is equal to the length of the input "47"), add "gp" to the result list.
           • Backtrack: Remove 'p' from the current combination to explore the next letter in "pqrs".
         • Repeat the process for 'q', 'r', and 's', resulting in "gq", "gr", "gs" being added to the results list after each complete iteration.
       • Backtrack to 'g': After exploring all combinations starting with 'g', remove 'g' from the current combination to backtrack and explore combinations starting with the next letter in "ghi".
     • Repeat the entire process for 'h' as the starting letter:
       • For 'h' + "pqrs", the combinations "hp", "hq", "hr", "hs" are generated and added to the results list.
     • Finally, repeat the process for 'i':
       • For 'i' + "pqrs", generate and add "ip", "iq", "ir", "is" to the results list.
   • The recursive function continues this pattern until all combinations have been explored and added to the results list.

5. Completion: Once the recursive function has explored all combinations, the algorithm ends. The results list now contains all possible combinations: ["gp", "gq", "gr", "gs", "hp", "hq", "hr", "hs", "ip", "iq", "ir", "is"].

6. Return Results: The list of combinations is returned as the output of the algorithm.

Code