给出手机九宫格输入法输入的数字序列（0到4个数），问可能有多少种英文字母组合方式，简单DFS
写法一
1 #17
2 #Runtime: 13 ms (Beats 82.90%)
3 #Memory: 13.3 MB (Beats 92.95%)
4
5 class Solution(object):
6 def letterCombinations(self, digits):
7 """
8 :type digits: str
9 :rtype: List[str]
10 """
11 if not digits:
12 return []
13 self.num_dict = {'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']}
14 self.ans = []
15 def dfs(t, k):
16 if k == len(digits):
17 self.ans.append(t)
18 return
19 for i in self.num_dict[digits[k]]:
20 t = t + i
21 dfs(t, k + 1)
22 t = t[:-1]
23 dfs("", 0)
24 return self.ans
写法二
1 #17
2 #Runtime: 28 ms
3 #Memory Usage: 13.5 MB
4
5 class Solution(object):
6 def DFS(self, s, digits):
7 if len(s) == len(digits):
8 self.ans.append(s)
9 return
10 for i in self.num_dict[digits[len(s)]]:
11 s = s + i
12 self.DFS(s, digits)
13 s = s[:-1]
14
15 def letterCombinations(self, digits):
16 """
17 :type digits: str
18 :rtype: List[str]
19 """
20 self.num_dict = {'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']}
21 self.ans = []
22 if digits:
23 self.DFS("", digits)
24 return self.ans