1 题目描述
给定一个包含数字[2-9]的字符串(闭区间),求数字可以代表的所有可能的字母组合。数字与字母的映射关系与手机号码簿相同(如下图),注意数字1未映射任何字母。
例子:
输入:“23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]
说明:虽如上例子所得组合为字母序,本题不对组合中字母顺序作要求。
题目出处:
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
2 解决思路
从第一个数字起,遍历其代表的所有字母,分别与子串形成的组合数组连接即为所求,所以采用递归,即可算得结果。
3 golang实现代码
https://github.com/leileiluoluo/leetcode/blob/master/17_Letter_Combinations_Of_A_Phone_Number/test.go
package main
import "fmt"
var (
mapping = map[byte][]string{
'2': {"a", "b", "c"},
'3': {"d", "e", "f"},
'4': {"g", "h", "i"},
'5': {"j", "k", "l"},
'6': {"m", "n", "o"},
'7': {"p", "q", "r", "s"},
'8': {"t", "u", "v"},
'9': {"w", "x", "y", "z"},
}
)
func letterCombinations(digits string) []string {
var combinations []string
if 0 == len(digits) {
return combinations
}
if 1 == len(digits) {
return mapping[digits[0]]
}
for _, letter := range mapping[digits[0]] {
for _, suffix := range letterCombinations(digits[1:]) {
combination := string(letter) + suffix
combinations = append(combinations, combination)
}
}
return combinations
}
func main() {
fmt.Println(letterCombinations("234"))
}