原题

解法1、2都是大佬的，题解链接

1、回溯

 1 class Solution:
 2     def letterCombinations(self, digits: str) -> List[str]:
 3         if not digits: return []
 4 
 5         phone = {'2':['a','b','c'],
 6                  '3':['d','e','f'],
 7                  '4':['g','h','i'],
 8                  '5':['j','k','l'],
 9                  '6':['m','n','o'],
10                  '7':['p','q','r','s'],
11                  '8':['t','u','v'],
12                  '9':['w','x','y','z']}
13                 
14         def backtrack(conbination,nextdigit):
15             if len(nextdigit) == 0:
16                 res.append(conbination)
17             else:
18                 for letter in phone[nextdigit[0]]:
19                     backtrack(conbination + letter,nextdigit[1:])
20 
21         res = []
22         backtrack('',digits)
23         return res

2、队列

 1 class Solution:
 2     def letterCombinations(self, digits: str) -> List[str]:
 3         if not digits: return []
 4         phone = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
 5         queue = ['']  # 初始化队列
 6         for digit in digits:
 7             for _ in range(len(queue)):
 8                 tmp = queue.pop(0)
 9                 for letter in phone[ord(digit)-50]:# 这里我们不使用 int() 转换字符串，使用ASCII码
10                     queue.append(tmp + letter)
11         return queue

3、与大佬的相比我的代码比较烂了

 1 class Solution:
 2     def letterCombinations(self, digits: str) -> List[str]:
 3         ans,dic,lens,cnt = [],{},len(digits),0
 4         dic['2'],dic['3'],dic['4'],dic['5'] = 'abc','def','ghi','jkl'
 5         dic['6'],dic['7'],dic['8'],dic['9'] = 'mno','pqrs','tuv','wxyz'
 6         for i in range(lens):
 7             if i == 0:
 8                 ans += ['']
 9             for j in range(len(ans)):
10                 for c in dic[digits[i]]:
11                     ans.append(ans[j] + c)
12         i = len(ans) - 1
13         while i >= 0 and len(ans[i]) == lens:
14             i -= 1
15         return ans[i + 1:]
16 
17