题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
输入：digits = “”
输出：[]
输入：digits = “2”
输出：[“a”,“b”,“c”]
思路
搜索问题，最开始想到回溯。可以用列表或者哈希表存储数字与字母的对应关系。
至于回溯的具体实现，想到了递归。
在实现上有这样几点细节：
- 数字和字母的对应关系定义成了类的成员变量。
- 最终返回的结果rs也定义成了类的成员变量。
- 递归函数记录每层生成的中间字符串。
- 递归函数逐层递归，在最深一层更新结果列表rs。
- 更新rs之后记得return！
- 由于rs定义成了类的成员变量，因此在函数内部必须将rs初始化！！
Python代码
class Solution:
table = [[], [], ['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m', 'n', 'o'],
['p', 'q', 'r', 's'], ['t', 'u', 'v'], ['w', 'x', 'y', 'z']]
rs = []
def dfs(self, digits, pos, curr_str=''):
if pos >= len(digits):
self.rs.append(curr_str)
return
for ch in self.table[int(digits[pos])]:
self.dfs(digits, pos+1, curr_str + ch)
def letterCombinations(self, digits):
self.rs = []
if len(digits) == 0:
return []
self.dfs(digits, 0)
return self.rs
