一、题设
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
二、基本思路
首先，对于电话数字和代表含义的映射，只要是python，几乎都可以想到用字典：
phone_dict = {'2':'abc', '3':'def', '4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
先举几个例子看一下：
eg1：input : digits = "23"
可以用两层循环去遍历每个digits[ i ],按个匹配即可。
eg2 : input : digits = "234"
同上，用三层循环
...综上，digits的字符串长度决定了循环的层数，而每次都是在变化的，所以我们这里优先考虑回溯：
回溯即递归，在这举digits = “23”为例，我们在遍历第一个digits[0]时也就是‘2’时，取出一个‘a’加入小数组中，当要取'b'时，赶快先取另一个'3'中的'd'加入小数组中，此时现在小数组已经形成一个目标子串，所以要将小数组加入最后大数组中。由此往复
注意：小数组每次回溯完都要出队，否则会造成数据冗余；有空字符串案例记得提前判断。
三、代码实现
class Solution(object):
def letterCombinations(self, digits):
if digits=="":
return []
phone_dict = {'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz',
}
res = [] # 存放结果列表
middle_res = [] # 存放中间结果列表
lens = len(digits) # 长度即middle_res中元素个数
index = 0 # 回溯下标
def recall(index):
if lens == index:
res.append("".join(middle_res))
else:
for item in phone_dict[digits[index]]:
middle_res.append(item)
recall(index + 1)
middle_res.pop()
recall(index)
return res四、效率总结
