0017. Letter Combinations of a Phone Number

# 17. Letter Combinations of a Phone Number#

## 题目 #

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

• DFS 递归深搜即可

## 代码 #

package leetcode

var (
letterMap = []string{
" ",    //0
"",     //1
"abc",  //2
"def",  //3
"ghi",  //4
"jkl",  //5
"mno",  //6
"pqrs", //7
"tuv",  //8
"wxyz", //9
}
res   = []string{}
final = 0
)

// 解法一 DFS
func letterCombinations(digits string) []string {
if digits == "" {
return []string{}
}
res = []string{}
findCombination(&digits, 0, "")
return res
}

func findCombination(digits *string, index int, s string) {
if index == len(*digits) {
res = append(res, s)
return
}
num := (*digits)[index]
letter := letterMap[num-'0']
for i := 0; i < len(letter); i++ {
findCombination(digits, index+1, s+string(letter[i]))
}
return
}

// 解法二 非递归
func letterCombinations_(digits string) []string {
if digits == "" {
return []string{}
}
index := digits[0] - '0'
letter := letterMap[index]
tmp := []string{}
for i := 0; i < len(letter); i++ {
if len(res) == 0 {
res = append(res, "")
}
for j := 0; j < len(res); j++ {
tmp = append(tmp, res[j]+string(letter[i]))
}
}
res = tmp
final++
letterCombinations(digits[1:])
final--
if final == 0 {
tmp = res
res = []string{}
}
return tmp
}

// 解法三 回溯（参考回溯模板，类似DFS）
var result []string
var dict = 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"},
}

func letterCombinationsBT(digits string) []string {
result = []string{}
if digits == "" {
return result
}
letterFunc("", digits)
return result
}

func letterFunc(res string, digits string) {
if digits == "" {
result = append(result, res)
return
}

k := digits[0:1]
digits = digits[1:]
for i := 0; i < len(dict[k]); i++ {
res += dict[k][i]
letterFunc(res, digits)
res = res[0 : len(res)-1]
}
}

Sep 6, 2020