电话号码的字母组合

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

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

示例 1：

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

示例 2：

输入：digits = "" 输出：[]

示例 3：

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

提示：

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

Related Topics 哈希表 字符串 回溯 👍 2805 👎 0

解题思路：

  • 构建映射表: 首先，我们需要建立一个数字到字母的映射表，例如 2 对应 abc，3 对应 def 等等。
  • 定义回溯函数: 该函数接受当前组合字符串和剩余数字作为参数。
  • 递归搜索:
    • 如果没有剩余数字，则将当前组合添加到结果列表中并返回。
    • 否则，遍历当前数字对应的字母:
    • 将当前字母添加到组合字符串中。
    • 对剩余数字进行递归调用。
    • 从组合字符串中删除当前字母（回溯）
func letterCombinations(digits string) []string {

	 // 建立数字到字母的映射关系
	 mapping := map[byte]string{
	 	'2': "abc",
	 	'3': "def",
	 	'4': "ghi",
	 	'5': "jkl",
	 	'6': "mno",
	 	'7': "pqrs",
	 	'8': "tuv",
	 	'9': "wxyz",
	 }
	 var result = []string{}
	 var backtrack func(res string, nextDigitStr string)
	 backtrack = func(res string, nextDigitStr string) {
	 	if len(nextDigitStr) == 0 {
	 		result = append(result, res)
	 		return
	 	}
     
	 	letters := mapping[nextDigitStr[0]]
	 	for _, let := range letters {
	 		backtrack(res+string(let), nextDigitStr[1:])
	 	}
	 }
     
	 backtrack("", digits)
	 return result
}