essay
hot100-电话号码的字母组合
#算法
hot100——电话号码的字母组合
给定一个仅包含数字 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'] 的一个数字。
解法
// 数字到字母的映射表，全局常量
var phoneMap = map[byte]string{
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz",
}
// letterCombinations 返回所有可能的字母组合
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
res := make([]string, 0)
backtrack(digits, 0, "", &res)
return res
}
// backtrack 是递归回溯函数
// digits: 输入的数字字符串
// index: 当前处理到的数字位置
// cur: 当前已经构建的字母组合（字符串）
// res: 指向结果集的指针
func backtrack(digits string, index int, cur string, res *[]string) {
// 递归终止：已经处理完所有数字，将当前组合加入结果集
if index == len(digits) {
*res = append(*res, cur)
return
}
// 获取当前数字对应的字母串
letters := phoneMap[digits[index]]
// 遍历每个可能的字母
for i := 0; i < len(letters); i++ {
// 将当前字母附加到 cur 上，递归处理下一个数字
// 注意：cur + string(letters[i]) 会产生新字符串，无需显式回溯
backtrack(digits, index+1, cur+string(letters[i]), res)
}
// 没有显式的撤销操作，因为每次递归传递的是新字符串值
}