How does backtracking apply to Letter Combinations of a Phone Number?

Backtracking allows the algorithm to explore every letter for each digit recursively, building partial combinations and pruning paths that cannot form valid sequences.

What is the maximum number of combinations for a 4-digit input?

The maximum is 4^4 = 256 combinations, considering digits like 7 or 9 which map to four letters, and this must be handled efficiently by pruning.

Can the output order be arbitrary?

Yes, the problem allows any order for the combinations, although a lexicographical order variant exists if sorting is needed after generation.

What should the function return for an empty string input?

An empty input string should return an empty list since there are no digits to map to letters, which avoids unnecessary recursion.

How do I optimize memory usage during backtracking?

Use in-place modification of a single combination buffer and backtrack by removing the last appended letter, instead of creating new strings at each recursion level.

#17

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例 1：输入： digits = "23" 输出： ["ad","ae","af","bd","be","bf","cd","c…

哈希表字符串回溯

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = "2"
输出：["a","b","c"]

提示：

1 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

lightbulb

解题思路

方法一：遍历

我们先用一个数组或者哈希表存储每个数字对应的字母，然后遍历每个数字，将其对应的字母与之前的结果进行组合，得到新的结果。

时间复杂度 $O(4^n)$ 。空间复杂度 $O(4^n)$ 。其中 $n$ 是输入数字的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        ans = [""]
        for i in digits:
            s = d[int(i) - 2]
            ans = [a + b for a in ans for b in s]
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(4^n * n), where n is the number of digits, because each digit can map up to 4 letters and each combination requires string construction. Space complexity is O(n) for the recursion stack or queue storage. These complexities directly reflect the backtracking search and pruning process used to generate all valid combinations efficiently.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you handle empty input correctly to avoid unnecessary recursion?
question_mark
Can you explain how pruning prevents generating invalid or partial combinations?
question_mark
Will you optimize the combination construction to avoid redundant string copies?

warning

常见陷阱

外企场景

error
Failing to prune paths when the current combination exceeds the input length, leading to unnecessary recursion.
error
Ignoring edge cases like empty input or single-digit input, which require returning empty or single-letter combinations.
error
Constructing new strings at every recursion step without backtracking, which increases memory usage and slows performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return letter combinations only for digits that map to exactly three letters, skipping digits like 7 and 9 with four letters.
arrow_right_alt
Count the total number of valid letter combinations without returning the sequences themselves, focusing on performance optimization.
arrow_right_alt
Generate combinations in lexicographical order rather than any order, adding a sorting constraint after backtracking.

help

常见问题

外企场景

继续练习

#126 单词接龙 II #140 单词拆分 II #691 贴纸拼词