Letter Combinations Of A Phone Number

Problem Description

rough nb

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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Solution Approach

This problem is a classic example of a backtracking or recursion problem. We need to explore all possible combinations of letters for the given digits.

The main idea is to build the combinations character by character. We can define a recursive function that takes the current combination being built and the remaining digits to process.

1. Mapping: We’ll use a hash map (or an array) to store the mapping from each digit (‘2’ through ‘9’) to its corresponding letters.
2. Base Case: The recursion stops when there are no more digits to process. At this point, the current combination we have built is a valid one, so we add it to our result list.
3. Recursive Step: For the current digit we are considering, we get its corresponding letters (e.g., ‘2’ -> “abc”). We then iterate through each of these letters. For each letter, we append it to our current combination and make a recursive call with the updated combination and the rest of the digits.
4. Backtracking: After the recursive call returns, we need to “undo” our choice. This means removing the letter we just added from the current combination, so we can explore other possibilities for the current digit’s letters. This “undoing” step is the essence of backtracking.

For an input like “23”:

• Start with an empty combination "" and digits "23".
• Process ‘2’:
  • Try ‘a’: Recurse with combination "a" and digits "3".
    • Process ‘3’:
      • Try ’d’: Recurse with "ad" and "". Base case hit. Add “ad” to results. Backtrack.
      • Try ’e’: Recurse with "ae" and "". Base case hit. Add “ae” to results. Backtrack.
      • Try ‘f’: Recurse with "af" and "". Base case hit. Add “af” to results. Backtrack.
  • Backtrack (remove ‘a’). Try ‘b’: Recurse with "b" and "3".
    • …and so on.

This systematic exploration ensures we generate all possible combinations.

Complexity Analysis

• Time: Let n be the number of digits in the input string. In the worst case, a digit maps to 4 letters (like ‘7’ or ‘9’). The recursion tree will have a depth of n. At each level, the number of branches can be up to 4. So, the total number of combinations is roughly 4^n. For each combination, we do n appends to form the string. So the time complexity is O(4^n * n).
• Space: The space complexity is determined by the recursion depth and the storage for the output. The recursion depth will be n, so the call stack uses O(n) space. The output list will store O(4^n) combinations of length n, but this is usually excluded from space complexity analysis unless specified. So, the space complexity is O(n) for the recursion stack.

Notes & Learnings

This problem is a great introduction to backtracking. The key pattern is to make a choice, recurse, and then undo the choice (backtrack). This allows for a systematic exploration of all possible solutions. The use of an index to track progress through the input string is a common technique in these types of recursive problems.