How Can We Generate Letter Combinations from a Phone Number?

When you think of a phone number, you likely think of digits, but there’s a fascinating connection to the alphabet that many people might overlook. Traditional phone keypads associate numbers with letters. For example, the number 2 corresponds to the letters A, B, and C, while 3 corresponds to D, E, and F. This association allows us to generate letter combinations from the digits of a phone number, and it’s a common question in technical interviews, particularly in programming roles.

Let’s dive into how we can accomplish this. Imagine we have a string representation of a digit sequence, like "23". Our goal is to generate all possible combinations of letters that those digits can represent. The mapping of digit to letters is as follows:

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

To solve this problem, we can use a backtracking approach. Backtracking is a technique for solving problems incrementally, attempting one option at a time and backtracking to try other options. Below is a Python example that illustrates this concept clearly.

python

1def letter_combinations(digits):
2    if not digits:
3        return []
4
5    # Mapping from digit to letters
6    digit_to_letters = {
7        '2': 'abc',
8        '3': 'def',
9        '4': 'ghi',
10        '5': 'jkl',
11        '6': 'mno',
12        '7': 'pqrs',
13        '8': 'tuv',
14        '9': 'wxyz'
15    }
16
17    def backtrack(index, path):
18        # If the current combination is complete, add it to the results
19        if index == len(digits):
20            combinations.append("".join(path))
21            return
22        
23        # Get the letters that the current digit maps to, and loop through them
24        letters = digit_to_letters[digits[index]]
25        for letter in letters:
26            path.append(letter)  # Choose a letter
27            backtrack(index + 1, path)  # Move to the next digit
28            path.pop()  # Backtrack
29
30    combinations = []
31    backtrack(0, [])
32    return combinations
33
34# Example usage:
35print(letter_combinations("23"))

In this code, the letter_combinations function first checks if the digits string is empty. The mapping between digits and corresponding letters is created in a dictionary. The inner function backtrack is defined to generate combinations. It takes the current index of digits and the current path of letters being formed.

When the cumulative length of the path matches the length of the digit string, a valid combination has been formed, and it’s added to the combinations list. The function loops through each letter corresponding to the current digit, appends a letter to the path, calls itself recursively to proceed to the next digit, and then pops the letter off when finished to try the next option.

Finally, when you call this function with a digit string like "23", the output will produce the combinations such as "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", and "cf". This approach efficiently explores all potential combinations via backtracking, allowing for a scalable solution regardless of the input length.