Letter Combinations of a Phone Number

Intuition

Each digit contributes exactly one letter to a combination, and the choices for one digit are independent of the choices for the others. This is a Cartesian product, which backtracking builds naturally: fix the letter for the current digit, move on to the next digit, and when we have chosen a letter for every digit the combination is complete. Undoing the last chosen letter lets us cycle through the remaining letters of the current digit.

Algorithm walkthrough

1. 1Return an empty list immediately when the input has no digits.
2. 2Keep a mapping from each digit character to its group of letters.
3. 3Recurse with an index into digits and the letters chosen so far.
4. 4When the index reaches the end of digits, store the assembled string.
5. 5Otherwise, for each letter of the current digit, append it, recurse to the next index, then remove it.

Implementation

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 = []

        def backtrack(index: int, path: str) -> None:
            if index == len(digits):
                result.append(path)
                return
            for letter in mapping[digits[index]]:
                backtrack(index + 1, path + letter)

        backtrack(0, "")
        return result