题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

电话号码

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

思路

回溯

class Solution:
    def letterCombinations(self, digits):
        lookup = {
            "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 helper(temp, i):
            '''
            
            :param temp: 表示即将形成的数组
            :param i: 代表第n个数字
            :return: 
            '''
            # 表示满足条件
            if i == n:
                res.append(temp)
                return 
            for a in lookup[digits[i]]:
                helper(temp + a, i + 1)
        helper([], 0)
        return res

AC17