【LeetCode】17. 电话号码的字母组合

链接：
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