给定一个仅包含数字 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]
