前言
假装开学好好学习
正文
问题来源
本问题来自leetcode上的172题。
问题描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
"2": []string{"a", "b", "c"},
"3": []string{"d", "e", "f"},
"4": []string{"g", "h", "i"},
"5": []string{"j", "k", "l"},
"6": []string{"m", "n", "o"},
"7": []string{"p", "q", "r", "s"},
"8": []string{"t", "u", "v"},
"9": []string{"w", "x", "y", "z"},
"0": []string{" "},
示例 1:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
分析：
很自然的回溯法 本人写的Go代码如下：
func letterCombinations(digits string) []string {
m := map[string][]string{
"2": []string{"a", "b", "c"},
"3": []string{"d", "e", "f"},
"4": []string{"g", "h", "i"},
"5": []string{"j", "k", "l"},
"6": []string{"m", "n", "o"},
"7": []string{"p", "q", "r", "s"},
"8": []string{"t", "u", "v"},
"9": []string{"w", "x", "y", "z"},
"0": []string{" "},
}
slices := [][]string{}
for index := range digits {
digit := string(digits[index])
if _, ok := m[digit]; ok {
slices = append(slices, m[digit])
}
}
return generateCombinations(slices)
}
func generateCombinations(slices [][]string) (ret []string) {
if len(slices) == 0 {
return
}
if len(slices) == 1 {
return slices[0]
}
for _, letter := range slices[0] {
tmpRets := generateCombinations(slices[1:])
for _, tmp := range tmpRets {
ret = append(ret, letter+tmp)
}
}
return
}
三个大循环解法
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
dict := map[rune][]rune{
'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'},
}
result := make([]string, 0)
runeSlice := make([][]rune, 0)
for _, r := range digits {
runeSlice = append(runeSlice, dict[r])
}
combine(runeSlice, make([]rune, len(runeSlice)), 0, &result)
return result
}
func combine(input [][]rune, current []rune, k int, result *[]string) {
if k == len(input) {
*result = append(*result, string(current))
} else {
for j := 0; j < len(input[k]); j++ {
current[k] = input[k][j]
combine(input, current, k+1, result)
}
}
}
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
dict := map[rune][]rune{
'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'},
}
result := make([]string, 0)
runeSlice := make([][]rune, 0)
for _, r := range digits {
runeSlice = append(runeSlice, dict[r])
}
combine(runeSlice, make([]rune, len(runeSlice)), 0, &result)
return result
}
func combine(input [][]rune, current []rune, k int, result *[]string) {
if k == len(input) {
*result = append(*result, string(current))
} else {
for j := 0; j < len(input[k]); j++ {
current[k] = input[k][j]
combine(input, current, k+1, result)
}
}
}
20200826 又做了一遍，双100
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return nil
}
m := map[byte]string {
'2' : "abc",
'3' : "def",
'4' : "ghi",
'5' : "jkl",
'6' : "mno",
'7' : "pqrs",
'8' : "tuv",
'9' : "wxyz",
}
tmp := make([]byte, 0)
var backtrack func(cur int)
res := []string{}
backtrack = func(cur int) {
if cur == len(digits) {
res = append(res, string(tmp))
return
}
key := m[digits[cur]]
for i := 0; i < len(key); i++ {
tmp = append(tmp, key[i])
backtrack(cur+1)
tmp = tmp[:len(tmp)-1]
}
}
backtrack(0)
return res
}
总结：
日常水一水
结语
不管怎么样好好加油。
