给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
200px-Telephone-keypad2.svg.png
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
我的方法：
直观感觉是用递归来处理，递归的关键是找到前一步和后一步返回值之间的关系，然后确立一个终止条件。用dict存储数字与字母的映射关系。
对于每个数字，将其代表的字符与之前所有数字的返回值拼接，即可得到结果。
完成题目的速度很快，但成绩一般：执行用时: 32 ms, 在Letter Combinations of a Phone Number的Python提交中击败了17.05% 的用户。内存消耗: 10.8 MB, 在Letter Combinations of a Phone Number的Python提交中击败了0.93% 的用户。
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
s=Solution()
# 用递归来处理
d={'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']}
# 异常处理
if len(digits)==0:
return []
# 终止条件
if len(digits)==1:
return d[digits]
else:
ans=[]
# 递归运算
for i in s.letterCombinations(digits[:-1]):
for j in d[digits[-1]]:
ans.append(i+j)
return ans
别人的方法：
基本思想和上述方法并无太大差别，同样是递归。区别仅在于：
- 这里用了两个函数来解决。
- 处理的顺序与我的方法不同，这里是将首个字符与后面所有字符连接，而我是把前面所有字符与最后一个字符连接。
执行效率并没有比我的方法更高，用时差不多：执行用时 : 36 ms, 在Letter Combinations of a Phone Number的Python提交中击败了10.39%的用户。内存消耗 : 10.8 MB, 在Letter Combinations of a Phone Number的Python提交中击败了0.93%的用户。
很奇怪，这个方法在最终的题解中提示只需要20ms，但我贴进去执行却花了36ms。
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
rlt = []
if len(digits)==0:
return rlt # 如果数字串长度为0，则说明没有返回值
dicts = {'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']}
rlt = self.letter_com_core(digits, dicts) #调用函数，得到最终的结果
return rlt
# 这是一个递归函数
def letter_com_core(self, digits, dicts):
rlt = []
# 基准条件，如果长度为1，就返回单字符列表
if len(digits)==1:
rlt = dicts[digits[0]]
return rlt
# 递归条件
# 主要分为两部分，头和尾，相互结合
for pre_char in dicts[digits[0]]:
back_chars = self.letter_com_core(digits[1:], dicts) # 得到尾
for single_back_char in back_chars:
rlt.append(pre_char+single_back_char)
return rlt
