题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

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

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路：

1. 回溯法(穷举法)：
   思路很简单，就是按照顺序枚举每一个数字对应的字母组合在一起。使用额外的函数 combination()将已产生的字母序列和剩下数字对应的字母结合起来。
   

class Solution:def letterCombinations(self, digits: str) -> List[str]:num_char_dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv','9': 'wxyz'}res = []# 组合问题def combination(prefix, next_digit):# 如果没有数字了，说明已经上图中的分支数已经走到尽头，只需要把过程中产生的所有的字母序列保存下来if next_digit == '':res.append(prefix)else:# 当前数字对应的每一个字母都会产生一个新的分支for letter in num_char_dict[next_digit[0]]:# 将当前字母添加入已有的字母的序列，继续剩下的数字combination(prefix + letter, next_digit[1:])if len(digits) == 0:return rescombination('', digits)return res

这种方法实质上还是 DFS，直到找到一个答案才保存下来，并返回上一分支点。时间和空间的复杂度都来自于递归，取决于N 叉树分支的个数，复杂度为$O(3^N×4^M)$，其中 N ，M 分别是包含3 个或 4 个字母的数字

2. 由于每个字母只与上一个字母有关，所以也可以采用动态规划。用 dp[i]表示前 i 个数字组成的所有组合，那么前 i+1 个数字的组合就是在 dp[i] 中每个组合末尾加上 i+1 对应的字母。

class Solution:def letterCombinations(self, digits: str) -> List[str]:num_char_dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv','9': 'wxyz'}if len(digits) == 0:return []# dp[i]表示前 i 个字母的所有组合dp = [[] for _ in range(len(digits))]dp[0] = list(num_char_dict[digits[0]])for i in range(1, len(digits)):dp[i] = [prefix + letter for prefix in dp[i-1] for letter in num_char_dict[digits[i]]]return dp[-1]

实际上我们不需要用二维数组保存每一步的结果，直接使用一维数组保存最新状态可以减少空间。最终所需的时间空间与方法一相同

class Solution:def letterCombinations(self, digits: str) -> List[str]:num_char_dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv','9': 'wxyz'}res = ['']if len(digits) == 0:return []for num in digits:res = [pre + suf for pre in res for suf in num_char_dict[num]]return res

动态规划的思想实质上是 BFS，每走一步就把所有的可能结果都保存下来，