給定一個包含 2-9 數字的字串，回傳所有該數字組合能代表的字母組合（按手機九宮格鍵盤的對應）。答案可以任意順序回傳。
Example:
Input: digits = “23” Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
Intuition
TIP
核心思路：每個數字對應 3-4 個字母，逐位數字展開所有可能的字母選擇，就是一棵回溯搜尋樹。
- 建立數字到字母的映射表
- 第一個數字有 3-4 種選擇，第二個數字也有 3-4 種選擇 …
- 每層選一個字母，遞迴到下一個數字，直到所有數字都處理完
Approaches
1. Iterative (BFS-style) — O(4^n * n) / O(4^n * n)
- Idea: 逐個數字處理，對每個數字，將現有的所有組合各自擴展新字母
- Time:
O(4^n * n)- n 為 digits 長度 - Space:
O(4^n * n)- 存所有組合
class Solution {
fun letterCombinations(digits: String): List<String> {
if (digits.isEmpty()) return emptyList()
val mapping = mapOf(
'2' to "abc", '3' to "def", '4' to "ghi", '5' to "jkl",
'6' to "mno", '7' to "pqrs", '8' to "tuv", '9' to "wxyz"
)
var result = listOf("")
for (digit in digits) {
val letters = mapping[digit]!!
result = result.flatMap { combo ->
letters.map { combo + it }
}
}
return result
}
}⭐ 2. Backtracking — O(4^n * n) / O(n)
- Idea: 逐位數字選擇字母，遞迴到底就得到一個完整組合
- Time:
O(4^n * n)- 最多 4^n 個組合 - Space:
O(n)- 遞迴深度
class Solution {
fun letterCombinations(digits: String): List<String> {
if (digits.isEmpty()) return emptyList()
val mapping = mapOf(
'2' to "abc", '3' to "def", '4' to "ghi", '5' to "jkl",
'6' to "mno", '7' to "pqrs", '8' to "tuv", '9' to "wxyz"
)
val result = mutableListOf<String>()
val sb = StringBuilder()
fun backtrack(index: Int) {
if (index == digits.length) {
result.add(sb.toString())
return
}
val letters = mapping[digits[index]]!!
for (letter in letters) {
sb.append(letter)
backtrack(index + 1)
sb.deleteCharAt(sb.lastIndex)
}
}
backtrack(0)
return result
}
}🔑 Takeaways
- Pattern: 多層選擇展開 → 回溯法的基本應用，每層選擇來自不同的候選集
- Key trick: 用 StringBuilder 比字串拼接更高效；映射表用 Map 或陣列都可以，陣列更快