17. Letter Combinations of a Phone Number

电话数字可以组合的字母组合

思路： dfs

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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)
	}

}