Letter Combinations Of A Phone Number Solution for Microsoft

Company: Microsoft · Difficulty: Medium · Topics: String, Backtracking, Hash Table

Problem Statement

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.

Digit to Letter Mapping:

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

Examples

Example 1:

Input: digits = "23"

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

Explanation:

2 maps to "abc", 3 maps to "def"

Combinations: "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"

Example 2:

Input: digits = ""

Output: []

Explanation:

No digits provided, so no combinations possible.

Example 3:

Input: digits = "2"

Output: ["a","b","c"]

Explanation:

2 maps to "abc", so the result is ["a","b","c"].

Example 4:

Input: digits = "9"

Output: ["w","x","y","z"]

Explanation:

9 maps to "wxyz", so the result is ["w","x","y","z"].

Intuition

The key insight is to use backtracking (recursion) to generate all possible combinations. For each digit, we need to try all possible letters that it can represent, and for each of those letters, we need to try all possible letters for the next digit, and so on.

This is essentially a Cartesian product of all the letter sets corresponding to each digit.

Approach

Approach 1: Backtracking (Optimal)

1. Create a mapping of digits to letters

2. Use recursion to build combinations

3. For each digit, try all possible letters

4. When we reach the end of digits, add the current combination to result

5. Backtrack by removing the last added letter

Approach 2: Iterative with Queue

1. Start with an empty string in the queue

2. For each digit, process all strings in the queue

3. For each string, append each letter of the current digit

4. Replace the queue with new combinations

5. Continue until all digits are processed

Approach 3: Iterative with Array

1. Start with an empty array

2. For each digit, create new combinations by appending letters

3. Build the result incrementally

4. Return the final array

Dry Run

Let's trace through Example 1: digits = "23"

Backtracking Approach:

Initialize: result = [], current = ""
Process digit '2' (maps to "abc"):
Try 'a': current = "a"
Process digit '3' (maps to "def"):
Try 'd': current = "ad" → add to result
Try 'e': current = "ae" → add to result
Try 'f': current = "af" → add to result
Backtrack: current = "a"
Try 'b': current = "b"
Process digit '3':
Try 'd': current = "bd" → add to result
Try 'e': current = "be" → add to result
Try 'f': current = "bf" → add to result
Backtrack: current = "b"
Try 'c': current = "c"
Process digit '3':
Try 'd': current = "cd" → add to result
Try 'e': current = "ce" → add to result
Try 'f': current = "cf" → add to result
Result: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Key Insights

1. Backtracking: Perfect for generating all combinations

2. Cartesian Product: Each digit contributes to all possible combinations

3. Base Case: When we reach the end of digits, we have a complete combination

4. State Management: Keep track of current combination being built

Edge Cases

1. Empty String: Return empty array

2. Single Digit: Return all letters for that digit

3. All Same Digit: Generate combinations with repeated letters

4. Long Digits: Handle multiple digits efficiently

Solutions

Best Approach: Backtracking

Time Complexity: O(4^n × n) where n is the number of digits
Space Complexity: O(n) for recursion stack
Key Idea: Use recursion to generate all combinations

Average Approach: Iterative with Queue

Time Complexity: O(4^n × n)
Space Complexity: O(4^n × n)
Key Idea: Use queue to build combinations iteratively

Worst Approach: Iterative with Array

Time Complexity: O(4^n × n)
Space Complexity: O(4^n × n)
Key Idea: Build combinations using array operations