17电话号码的字母组合

class Solution:
    def __init__(self):
        self.path = ''
        self.result = []
        self.dict = {}
        def push_dict():      # 建立映射关系
            self.dict[2] = 'abc'
            self.dict[3] = 'def'
            self.dict[4] = 'ghi'
            self.dict[5] = 'jkl'
            self.dict[6] = 'mno'
            self.dict[7] = 'pqrs'
            self.dict[8] = 'tuv'
            self.dict[9] = 'wxyz'
        push_dict()
    def letterCombinations(self, digits: str) -> List[str]:
        # 先想到暴力解法， 用x 个for 循环 嵌套，但是这个x 的数量 没法控制。我们很快想到用树结构配合上回溯的思路解决；
        # 先需要 建立一个映射关系；
        # 因为这不是在一个区间内 找组合，不需要 startindex 来内部划分 避免重复，我们只需要能跳转到别的区间即可；
        return self.letterCombinations_(digits,0)
    def letterCombinations_(self,digits,index) -> List[str]:  # index 来表明 用的是哪个区间。
        if index == len(digits):        # 这个是 树结构到底了的 返回触发。
            return self.result
        target = self.dict[int(digits[index])]
        for i in range(0,len(target)):
            self.path += target[i]
            if index == len(digits)-1:  # 叶子结点
                self.result.append(self.path)
                print(self.result)
            self.letterCombinations_(digits,index+1)
            self.path = self.path[:-1]
        return self.result