题目描述

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

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

示例:

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

说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

我的解法——回溯（AC）

这道题的思路很简单，假设输入的是”23”，2对应的是”abc”，3对应的是”edf”，那么我们在递归时，先确定2对应的其中一个字母（假设是a），然后进入下一层，穷举3对应的所有字母，并组合起来（”ae”，”ad”，”af”），当”edf”穷举完后，返回上一层，更新字母b，再重新进入下一层。这个就是backtracing的基本思想。
时间复杂度O(n)，空间复杂度O(n)
Beat 27%

class Solution(object):
    def __init__(self):
        self.dict = {'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']}
        self.res = []
        
    def dfs(self, digits, now_digit_index, now_res):
        if(now_digit_index >= self.length):
            self.res.append(now_res)
            return None
        for char in self.dict[digits[now_digit_index]]:
            self.dfs(digits, now_digit_index + 1, now_res + char)  # 注意这里，now_res + char后还要恢复为now_res
        
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        self.length = len(digits)
        if(self.length == 0):
            return []
        self.dfs(digits, 0, '')
        return self.res