💬 Discord
Sign In
NeetCode #500LC-17MediumBacktrackingNC 150NC 250
← Back to All Problems

#500 · #17 · Letter Combinations of a Phone Number(电话号码的字母组合)

📌 Problem Statement & Constraints

Given a string digits containing digits from 2 to 9, return all possible letter combinations that the number could represent, using the standard phone keypad mapping. Constraints: 0 <= digits.length <= 4.

💡 Core Algorithmic Approaches

  1. Each digit maps to a fixed set of letters, so the answer is the Cartesian product of those sets.
  2. A DFS over the digit positions builds the combinations.
  3. The empty input must return an empty list, not a list containing the empty string.
  4. An iterative alternative expands the result list one digit at a time.

💻 Benchmark Python3 Implementation

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []                      # empty input -> empty output
        keypad = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
                  "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []

        def dfs(i: int, path: str) -> None:
            if i == len(digits):
                res.append(path)
                return
            for ch in keypad[digits[i]]:
                dfs(i + 1, path + ch)

        dfs(0, "")
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(4^n * n) where n is the number of digits: at most four letters per digit.
💾 Space Complexity
O(n) for the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Returning [""] for empty input: the contract requires an empty list.
  • Getting the 7 and 9 mappings wrong: they have four letters (pqrs, wxyz), not three.
  • Trying to build the combinations iteratively with nested loops: the depth is dynamic, so recursion is the natural fit.
  • Assuming digits are 0-9: the input excludes 0 and 1, which have no letters.