LeetCode 17 Solution - Letter Combinations of a Phone Number

Problem Statement (LeetCode 17)

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:

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

Example 1:

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

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a", "b", "c"]

---

Optimal Approach: Backtracking

Intuition

This problem can be approached effectively using backtracking. For each digit in the input string, we need to generate all possible combinations of the corresponding letters. This is a typical case of combinatorial generation.

Why Backtracking Works

1. Combinatorial Explosion: Each digit maps to a set of letters, and we need to explore all possible combinations. Backtracking allows us to explore all possibilities and efficiently build the combinations.
2. Depth-First Search (DFS): The algorithm works by considering each possible letter for the current digit, then recursively proceeding to the next digit.
3. Pruning: The recursion will terminate when all digits have been processed, ensuring that we generate exactly the required combinations.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) {
            return {};  // Return empty if no digits are provided
        }

        // Mapping digits to corresponding characters
        vector<string> mapping = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        vector<string> result;
        string current;
        backtrack(digits, 0, current, result, mapping);
        return result;
    }

private:
    void backtrack(const string& digits, int index, string& current, vector<string>& result, const vector<string>& mapping) {
        // If the current combination is complete, add it to the result
        if (index == digits.size()) {
            result.push_back(current);
            return;
        }

        // Get the current digit
        int digit = digits[index] - '0';
        string letters = mapping[digit];

        // Try each letter corresponding to the current digit
        for (char letter : letters) {
            current.push_back(letter);  // Add the letter to the current combination
            backtrack(digits, index + 1, current, result, mapping);  // Recurse for the next digit
            current.pop_back();  // Backtrack, remove the last letter
        }
    }
};

---

Step-by-Step Explanation of Code

1. Input Check:
   If the digits string is empty, we return an empty list because no combinations are possible.

2. Mapping Digits to Letters:
   We use a vector mapping where each index corresponds to a digit (2-9), and each entry holds the string of letters that the digit maps to. For example, index 2 holds the string "abc", and index 3 holds "def".

3. Backtracking Function:
   The backtrack function recursively builds the letter combinations. It accepts the following parameters:

   • digits: The input string of digits.
   • index: The current position in the digits string we are processing.
   • current: The current combination of letters being formed.
   • result: The vector to store the valid combinations once they are completed.
   • mapping: The array of letter strings corresponding to each digit.

4. Base Case:
   When index equals the size of digits, we have successfully formed a combination of letters, so we add it to result.

5. Recursive Case:
   For each character corresponding to the current digit, we add it to the current string, recurse for the next digit, and then backtrack by removing the character and trying the next possibility.

6. Return the Result:
   Once the recursion finishes, the result vector contains all the combinations, which is then returned.

---

Dry Run with Example

Input: digits = "23"

Step 1: Start the backtracking with index = 0, current = "", and an empty result.

• At index = 0, the digit is '2' which maps to the letters "abc".

  • For 'a', current = "a", recurse to index = 1.
  • For 'b', current = "b", recurse to index = 1.
  • For 'c', current = "c", recurse to index = 1.

• At index = 1, the digit is '3' which maps to the letters "def".

  • For 'd', add "ad", recurse to index = 2, add to result.
  • For 'e', add "ae", recurse to index = 2, add to result.
  • For 'f', add "af", recurse to index = 2, add to result.

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

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Backtracking (Current Approach)	O(4^n)	O(n)	This approach efficiently generates all combinations in a depth-first manner.
Iterative Approach (Queue)	O(4^n)	O(n)	Can be used to iteratively build the combinations, but is more complicated compared to recursion.
Memoization (DP)	O(4^n)	O(n)	Not necessary since we aren't repeating calculations that can be memoized.

---

Why Backtracking is the Best

• Time Complexity: O(4^n), where n is the length of the input string. This is because there are up to 4 options for each digit (since the longest mapping has 4 letters: "pqrs").
• Space Complexity: O(n), where n is the length of the input string, for the recursion stack and the current string.
• Clean and Efficient: Backtracking is a clean and direct way to generate combinations in a depth-first manner, ensuring all possible combinations are covered.

---

Complexity Analysis

• Time Complexity: O(4^n)
  There are up to 4 letters for each digit, so in the worst case, there are 4^n combinations. Each recursive call processes one combination.

• Space Complexity: O(n)
  The recursion depth is at most n (the length of the input), and each recursive call holds a string of length n in the current variable.

---

Conclusion

✅ Best Approach: Backtracking
✅ Time Complexity: O(4^n)
✅ Space Complexity: O(n)
✅ Optimal for Generating Combinations Efficiently

Recommended Problems for Practice

1. Phone Number Combinations (LeetCode 17)
2. Permutations (LeetCode 46)
3. Combinations (LeetCode 77)

🚀 Master the Backtracking Technique to Generate All Possible Combinations!