前往此题

又遇到了组合类的题，这种想都不用想，直接回溯伺候

算法过程

1. 创建键盘分类数据phone, 用于查找键盘对应数据
2. 回溯字符串digits并从phone中提取数据
3. 回溯过程：
   1. 以23为例，先遍历2，从phone中获取数组[a,b,c]，并将元素赋值给letter
   2. 此时letter为a, 与上一轮拼接成的字符串conbition拼接, 并继续回溯3
      1. 此时分成三条线：a, b, c分别取拼接d,e,f
      2. 然后看digits的遍历状态，如果到末尾了，说明单层的遍历结束了，将拼接后的结果放入到结果res中
   3. 然后如此往复
4. 最后返回res

代码

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []

        phone = { "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']}
        
        def backtrack(conbition, next):
            if len(next) == 0: res.append(conbition)
            else:
                for letter in phone[next[0]]:
                    backtrack(conbition + letter, next[1:])
        res = []
        backtrack('', digits)
        return res