leetcode17. 电话号码的字母组合

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

数字到字母的映射

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

#python
class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        ldict={}
        ldict['2'] = "abc"
        ldict['3'] = "def"
        ldict['4'] = "ghi"
        ldict['5'] = "jkl"
        ldict['6'] = "mno"
        ldict['7'] = "pqrs"
        ldict['8'] = "tuv"
        ldict['9'] = "wxyz"
        if digits=="":return []
        result=['']
        for digit in digits:
            lst = ldict[digit]
            newresult = []
            for x in result:
                for y in lst:
                    newresult.append(x+y)
            result = newresult
        return result

#python 回溯（想象成一棵树，自底向上遍历）
class Solution:
    # @param {string} digits
    # @return {string[]}
    def letterCombinations(self, digits):
        mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', 
                   '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        if len(digits) == 0:
            return []
        if len(digits) == 1:
            return list(mapping[digits[0]])
        prev = self.letterCombinations(digits[:-1])
        additional = mapping[digits[-1]]
        return [s + c for s in prev for c in additional]