Letter Combinations of a Phone Number

Problem

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

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 = "2"
Output: ["a","b","c"]

Constraints:

• 1 <= digits.length <= 4

• digits[i] is a digit in the range ['2', '9'].

Pattern

Hash Table, String, Backtracking

Approaches

Backtracking

Explanation

First map each digit to a group of letters. We can generate letter combinations by appending each letter in the group to each combination.

Code

def letterCombinations(digits: str) -> list[str]:
    """Generate letter combinations from a phone number."""
    if len(digits) == 0:
        return []

    digit2group = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }

    letter_groups = []
    for digit in digits:
        letter_groups.append(digit2group[digit])

    letter_combinations = [""]
    for group in letter_groups:
        letter_combinations = [
            combination + letter
            for letter in group
            for combination in letter_combinations
        ]

    return letter_combinations

Test

>>> from letter_combinations_of_a_phone_number__backtracking import letterCombinations
>>> letterCombinations('23')
['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']
>>> letterCombinations('')
[]
>>> letterCombinations('2')
['a', 'b', 'c']

Complexity

\(n\) is the length of digits.

Measure	Complexity	Notes
Time	\(O(4^n)\)	at each step, we append 4 letters to each combination
Auxiliary Space	\(O(1)\)

letter_combinations_of_a_phone_number__backtracking.letterCombinations(digits: str) → list[str]

Generate letter combinations from a phone number.