【递归 &回溯】Leecode-17. 电话号码的字母组合

【题目】

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

【题解】

题解1：

• 思路

     直接笛卡尔积

• 复杂度

         时间复杂度：O(n)，空间复杂度：O(n)

• 代码

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        num_al= {
            '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'],
        }
        res = []
        for d in itertools.product(*[num_al[i] for i in digits]):
            res.append(''.join(d))
        return res