题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
例：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
方法：递归、回溯
- 判断字符串是否为空
- 按照数字到字母的映射定义一个字典，数字部分为键 key，字母部分为值 value。result 表示所有符合要求的字符串，path 表示当前将要组成字符串的字母（们），index 表示字符串 digits 的索引
backtrack 部分：
- 当 path 的长度等于字符串 digits 的长度时，表示此时 path 中存储的字母个数已等于要求的字母个数，则将 path 中的字母组合成字符串，加入 result 中
- 当 path 的长度不等于字符串 digits 的长度时，表示存在数字对应的字母未加入 path。num 表示此时该从字符串 digits 中获取的数字，使用键 num 查找字典中相应的字母字符串，通过循环实现 path 的建立
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
dict = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
result = []
path = []
def backtrack(index):
if len(path) == len(digits):
result.append("".join(path))
return None
num = digits[index]
for letter in dict[num]:
path.append(letter)
backtrack(index + 1)
path.pop()
backtrack(0)
return result
