链接：
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
思路：
利用深度优先遍历
遍历两个空间
第一个空间是digits，命名为space1
第二个空间是digits的每一位自身的空间，命名为space2
关键是遍历完每一个space2之后，如何转到space1的下一个space2中
代码
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
dic = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
n = len(digits)
if n == 0:
return []
res = []
tmp_cur = ''
def backtrack(tmp_cur, i):
if i == n:
res.append(tmp_cur)
return
for s in dic[digits[i]]:
# 这里通过参数 i + 1 ,来转到下一个空间
backtrack(tmp_cur + s, i + 1)
backtrack(tmp_cur, 0)
return res