17. 电话号码的字母组合

mid

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

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

示例 1：

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

示例 2：

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

示例 3：

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

回溯

经典的全排列，比组合简单多了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var phoneMap map[string]string = map[string]string{
	"2": "abc",
	"3": "def",
	"4": "ghi",
	"5": "jkl",
	"6": "mno",
	"7": "pqrs",
	"8": "tuv",
	"9": "wxyz",
}

func letterCombinations(digits string) []string {
    if digits == "" {
		return []string{}
	}
	res := make([]string, 0)
	var bt func(index int, combination string)
	bt = func(index int, combination string) {
		if index == len(digits) {
			res = append(res, combination)
			// tmpStr = ""
			return
		}

		for _, word := range phoneMap[string(digits[index])] {
			bt(index+1, combination+string(word))
		}
	}
	bt(0, "")
	return res
}