LeetCode每日一题——T17. 电话号码的字母组合（中），递归

很明显，这是一个涉及 递归 的问题。

可以将题目理解为将每个数字“转译”成字母，问一串数字有多少种“转译”结果。
则每“转译”一个数字，相当于求剩余数字的“转译”结果，然后将结果拼接到当前数字对应的三或四种字母后面。这正是递归的思想。采用递归进行求解：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        _dict = {
            "2" : "abc",
            "3" : "def",
            "4" : "ghi",
            "5" : "jkl",
            "6" : "mno",
            "7" : "pqrs",
            "8" : "tuv",
            "9" : "wxyz"
        }
        if not digits:
            return []
        
        n = len(digits)
        res = []
        
        def recurNum(i, temp):
            if i == n:
                res.append(temp)
                return
            for num_letter in _dict[digits[i]]:
                recurNum(i + 1, temp + num_letter)
        
        recurNum(0, "")
        
        return res