电话数字可以组合的字母组合
思路： dfs
Python:
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
# 5 star
# dfs, ac了但是很慢，看看更好的解法
if digits == "":
return []
num_map = {
'1': [],
'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']
}
rs = []
path = ""
self.dfs(digits, rs, path, num_map)
return rs
def dfs(self, digits, rs, path, num_map):
if digits == "":
rs.append(path)
return
chars = num_map.get(digits[0], [])
for char in chars:
self.dfs(digits[1:], rs, path+char, num_map)Go:
func letterCombinations(digits string) []string {
digits_list := []byte(digits)
if len(digits_list) == 0 {return []string{}}
letterMap := map[string][]string{
"1": []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"},
}
ret := []string{}
retP := &ret
dfs(digits_list, "", retP, letterMap)
return *retP
}
func dfs(digits_list []byte, path string, retP *[]string, letterMap map[string][]string) {
if len(digits_list) == 0 {
*retP = append(*retP, path)
return
}
num := string(digits_list[0])
letters := letterMap[num]
for _, v := range letters {
dfs(digits_list[1:], path + v, retP, letterMap)
}
}