View on NeetCode
View on LeetCode

Problem

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.

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"]

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Solution

Approach: Backtracking

The key insight is to build combinations by choosing one letter from each digit’s mapping, using backtracking to explore all choices.

Implementation

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

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

        result = []

        def backtrack(index, path):
            if index == len(digits):
                result.append(path)
                return

            for letter in phone[digits[index]]:
                backtrack(index + 1, path + letter)

        backtrack(0, "")
        return result

Iterative Approach:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

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

        result = [""]
        for digit in digits:
            result = [combo + letter
                      for combo in result
                      for letter in phone[digit]]

        return result

Complexity Analysis

  • Time Complexity: O(4^n * n), where n is the length of digits. In worst case (digits 7 or 9), each digit has 4 letters. We create 4^n combinations, each taking O(n) to build.
  • Space Complexity: O(n) for recursion depth (not counting output).

Key Insights

  1. Cartesian Product: The problem is essentially computing the Cartesian product of letter sets for each digit.

  2. Sequential Building: We build combinations one digit at a time, appending letters from each digit’s mapping.

  3. Simple Backtracking: Unlike other backtracking problems, we don’t need to check constraints - every combination is valid.

  4. Iterative Alternative: The iterative approach is elegant for this problem since we’re simply extending all existing combinations with new letters.

  5. Empty Input: Handle empty input as a special case returning an empty list.