题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
- 输入：digits = “23”
- 输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
示例 3：
- 输入：digits = “2”
- 输出：[“a”,“b”,“c”]
提示：
0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。
解法一：回溯
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
|
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
record := map[byte]string{
'2': "abc", '3': "def", '4': "ghi", '5': "jkl",
'6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
}
n := len(digits)
var ans []string
var tmp []rune
var backtracking func(idx int)
backtracking = func(idx int) {
if idx >= n {
ans = append(ans, string(tmp))
return
}
for _, cur := range record[digits[idx]] {
tmp = append(tmp, cur)
backtracking(idx + 1)
tmp = tmp[:len(tmp)-1]
}
}
backtracking(0)
return ans
}
|
