17. 电话号码的字母组合
- 题目-中等难度
- 示例
- 1. 回溯
题目-中等难度
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]
提示：
- 0 <= digits.length <= 4
- digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1. 回溯
时间
36ms
击败 91.73%使用 Python3 的用户
内存
17.18MB
击败 5.21%使用 Python3 的用户
class Solution:def letterCombinations(self, digits: str) -> List[str]:# 数字到相应字母的映射m = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}# 确保在输入为空的情况下直接返回空列表if not digits:return []li = []# 用于存储所有组合的列表lli = [] # 临时列表，用于存储当前组合# 回溯函数def backtrack(index: int):# 如果当前索引等于数字的长度# 完成回溯得到一个完整的组合if index == len(digits):li.append("".join(lli))else:# 获取当前索引处的数字d = digits[index]# 循环遍历当前数字对应的字母for i in m[d]:# 将字母添加到当前组合中lli.append(i) # 移至下一个数字backtrack(index + 1)# 删除最后一个字母以进行回溯lli.pop() # 从第一个数字开始回溯。backtrack(0)# 返回所有组合的列表。return li