Letter Combinations of a Phone Number

Build up the result list by repeatedly taking the Cartesian product with the next digit’s letters: start with [""], and for each digit, form every combination of an existing partial string with every letter of that digit.

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []
        mapping = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
        }
        combos = ['']
        for digit in digits:
            combos = [prefix + letter for prefix in combos for letter in mapping[digit]]
        return combos

Correct and reasonably efficient, but it materializes a full intermediate list after every digit rather than exploring the tree depth-first — for problems with pruning opportunities this pattern would waste work, though here (with no invalid combinations to skip) it costs the same asymptotically as backtracking.

Recurse through digits index by index. At each call, try every letter mapped to the current digit: append it to path, recurse into the next digit, then remove it. A combination is complete once path covers every digit.

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []
        mapping = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
        }
        result = []
        path = []

        def backtrack(index):
            if index == len(digits):
                result.append(''.join(path))
                return
            for letter in mapping[digits[index]]:
                path.append(letter)
                backtrack(index + 1)
                path.pop()

        backtrack(0)
        return result

Watch the path fill to length 2, get recorded, then shrink by one letter before the next sibling is tried — that pop is the backtrack.

Complexity: letting n = len(digits), each digit contributes at most 4 choices (digits 7 and 9 have 4 letters), so there are up to 4^n complete combinations, each built in O(n) → O(4^n · n) time. Recursion depth and path are bounded by n → O(n) auxiliary space (excluding the output).