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