给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
![](https://github.xin/wp-content/uploads/2023/07/6ffd9f622a62a37.png)
示例 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']
的一个数字。
题解:
回溯法:
func letterCombinations(digits string) []string {
letterMap := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
var s string
var result []string
var backtracking func(digits string, index int)
backtracking = func(digits string, index int) {
if index == len(digits) {
result = append(result, s)
return
}
digit := digits[index] - '0'
letter := letterMap[digit]
for i := 0; i < len(letter); i++ {
s += string(letter[i])
backtracking(digits, index+1)
s = s[:len(s)-1]
}
}
if digits != "" {
backtracking(digits, 0)
}
return result
}
回溯法(隐藏了回溯过程):
func letterCombinations(digits string) []string {
letterMap := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
//var s string
var result []string
var backtracking func(digits string, index int, s string)
backtracking = func(digits string, index int, s string) {
if index == len(digits) {
result = append(result, s)
return
}
digit := digits[index] - '0'
letter := letterMap[digit]
for i := 0; i < len(letter); i++ {
backtracking(digits, index+1, s+string(letter[i]))
}
}
if digits != "" {
backtracking(digits, 0, "")
}
return result
}
评论前必须登录!
注册