【Leetcode】17—Letter Combinations

一、题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例：

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

二、代码实现

回溯算法、递归深搜

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        
        mapdict = {'2':'abc', '3':'def', '4':'ghi', '5': 'jkl', '6': 'mno',
                  '7':'pqrs', '8':'tuv', '9':'wxyz'}
        
        def dfs(digits, path, res):
            if len(digits) == 0: return
            if len(digits) == 1:
                chars = mapdict[digits]
                for char in chars:
                    res.append(path + char)
                return
            
            chars = mapdict[digits[0]]
            for char in chars:
                dfs(digits[1:], path + char, res)
                               
        res = []
        dfs(digits, '', res)
        
        return res