LeetCode 17: Letter Combinations of a Phone Number (Backtracking DFS)
LeetCode 17StringBacktrackingDFSToday we solve LeetCode 17 - Letter Combinations of a Phone Number.
Source: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
English
Problem Summary
Given a digit string digits containing characters from 2 to 9, return all possible letter combinations based on the telephone keypad mapping. Return an empty list when digits is empty.
Key Insight
Each digit contributes one set of choices, so the problem is naturally a decision tree. We build combinations position by position with DFS backtracking: choose a letter for current digit, recurse to next digit, then undo the choice.
Brute Force and Limitations
A brute-force mindset still becomes recursive enumeration because each position has 3 or 4 options. The key is implementing this enumeration cleanly and efficiently, avoiding repeated string copying inside deep recursion.
Optimal Algorithm Steps
1) If digits is empty, return empty result immediately.
2) Prepare keypad mapping: 2->abc, 3->def, ..., 9->wxyz.
3) Start DFS from index 0 with an empty path buffer.
4) At each index, iterate all mapped letters for that digit.
5) Append one letter, recurse to next index, then pop it (backtrack).
6) When index reaches digits.length(), record one full combination.
Complexity Analysis
Let n = digits.length(). Time complexity is O(4^n * n) in the worst case (all digits are 7/9 with 4 choices, and each output string length is n). Space complexity is O(n) for recursion path excluding output.
Common Pitfalls
- Forgetting to handle empty input and returning [""] incorrectly.
- Not backtracking (missing pop/delete), causing polluted paths.
- Using wrong keypad mapping for digits 7 and 9 (four letters).
- Reusing mutable buffers incorrectly when adding answers.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static final String[] MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if (digits == null || digits.length() == 0) return ans;
StringBuilder path = new StringBuilder();
dfs(digits, 0, path, ans);
return ans;
}
private void dfs(String digits, int idx, StringBuilder path, List<String> ans) {
if (idx == digits.length()) {
ans.add(path.toString());
return;
}
String letters = MAP[digits.charAt(idx) - '0'];
for (int i = 0; i < letters.length(); i++) {
path.append(letters.charAt(i));
dfs(digits, idx + 1, path, ans);
path.deleteCharAt(path.length() - 1);
}
}
}func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
mp := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
res := make([]string, 0)
path := make([]byte, 0, len(digits))
var dfs func(int)
dfs = func(idx int) {
if idx == len(digits) {
res = append(res, string(path))
return
}
letters := mp[digits[idx]-'0']
for i := 0; i < len(letters); i++ {
path = append(path, letters[i])
dfs(idx + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return res
}class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
string path;
function<void(int)> dfs = [&](int idx) {
if (idx == (int)digits.size()) {
ans.push_back(path);
return;
}
string letters = mp[digits[idx] - '0'];
for (char c : letters) {
path.push_back(c);
dfs(idx + 1);
path.pop_back();
}
};
dfs(0);
return ans;
}
};class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mp = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
}
ans = []
path = []
def dfs(idx: int) -> None:
if idx == len(digits):
ans.append("".join(path))
return
for ch in mp[digits[idx]]:
path.append(ch)
dfs(idx + 1)
path.pop()
dfs(0)
return ansvar letterCombinations = function(digits) {
if (!digits || digits.length === 0) return [];
const map = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
};
const ans = [];
const path = [];
const dfs = (idx) => {
if (idx === digits.length) {
ans.push(path.join(''));
return;
}
const letters = map[digits[idx]];
for (const ch of letters) {
path.push(ch);
dfs(idx + 1);
path.pop();
}
};
dfs(0);
return ans;
};中文
题目概述
给定只包含 2-9 的数字字符串 digits，根据手机按键映射返回所有可能的字母组合；若输入为空，返回空数组。
核心思路
每一位数字都对应一个“可选字符集合”，本质就是一棵决策树。使用回溯 DFS：逐位选择字符，递归进入下一位，返回时撤销选择。
暴力解法与不足
该题天然需要枚举所有有效组合。关键不在“是否枚举”，而在于如何高效实现枚举：用可变路径容器做 append/pop，避免深层递归中频繁新建字符串。
最优算法步骤
1）若 digits 为空，直接返回空结果。
2）建立按键映射表：2->abc, 3->def, ..., 9->wxyz。
3）从下标 0 开始 DFS，维护当前路径 path。
4）对当前数字对应的每个字母进行尝试。
5）加入字母后递归，再撤销该字母（回溯）。
6）当下标到达末尾时，路径即为一个完整组合，加入答案。
复杂度分析
设 n = digits.length()。最坏情况下（全是 7/9）每位有 4 种选择，时间复杂度约为 O(4^n * n)；额外空间复杂度（不含输出）为 O(n)。
常见陷阱
- 空输入处理错误，返回了 [""]。
- 回溯遗漏撤销步骤，导致路径污染。
- 7 和 9 的映射写错（它们是 4 个字母）。
- 把可变对象直接塞进答案，导致结果被后续修改。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static final String[] MAP = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if (digits == null || digits.length() == 0) return ans;
StringBuilder path = new StringBuilder();
dfs(digits, 0, path, ans);
return ans;
}
private void dfs(String digits, int idx, StringBuilder path, List<String> ans) {
if (idx == digits.length()) {
ans.add(path.toString());
return;
}
String letters = MAP[digits.charAt(idx) - '0'];
for (int i = 0; i < letters.length(); i++) {
path.append(letters.charAt(i));
dfs(digits, idx + 1, path, ans);
path.deleteCharAt(path.length() - 1);
}
}
}func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
mp := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
res := make([]string, 0)
path := make([]byte, 0, len(digits))
var dfs func(int)
dfs = func(idx int) {
if idx == len(digits) {
res = append(res, string(path))
return
}
letters := mp[digits[idx]-'0']
for i := 0; i < len(letters); i++ {
path = append(path, letters[i])
dfs(idx + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return res
}class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ans;
string path;
function<void(int)> dfs = [&](int idx) {
if (idx == (int)digits.size()) {
ans.push_back(path);
return;
}
string letters = mp[digits[idx] - '0'];
for (char c : letters) {
path.push_back(c);
dfs(idx + 1);
path.pop_back();
}
};
dfs(0);
return ans;
}
};class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mp = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
}
ans = []
path = []
def dfs(idx: int) -> None:
if idx == len(digits):
ans.append("".join(path))
return
for ch in mp[digits[idx]]:
path.append(ch)
dfs(idx + 1)
path.pop()
dfs(0)
return ansvar letterCombinations = function(digits) {
if (!digits || digits.length === 0) return [];
const map = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
};
const ans = [];
const path = [];
const dfs = (idx) => {
if (idx === digits.length) {
ans.push(path.join(''));
return;
}
const letters = map[digits[idx]];
for (const ch of letters) {
path.push(ch);
dfs(idx + 1);
path.pop();
}
};
dfs(0);
return ans;
};
Comments