难度：Medium.
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解析：
这里的相关标签是：字符串，回溯算法.
给出的官方方法是回溯算法，但是看到这道题我的第一个想法是动态填充表格（即动态规划）。
比如，输入："233"。
先填充第一维，
| a | b | c |
|---|
再填充第二维，
| ad | bd | cd |
|---|---|---|
| ae | be | ce |
| af | bf | cf |
再填充第三维，
| add | bdd | cdd |
|---|---|---|
| ade | bde | cde |
| adf | bdf | cdf |
| aed | bed | ced |
|---|---|---|
| aee | bee | cee |
| aef | bef | cef |
| afd | bfd | cfd |
|---|---|---|
| afe | bfe | cfe |
| aff | bff | cff |
代码：
def letterCombinations(digits):
dictionary = {'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 digits == '':
return []
ans = ['']
for d in digits:
ans = [c + cc for c in ans for cc in dictionary[d]]
return ans
每一次对于新维度的填充都遵循同一个公式：
ans = [c + cc for c in ans for cc in dictionary[d]]
