type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个仅包含数字
2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。

注意 1 不对应任何字母。
示例 1:
示例 2:
示例 3:
提示:
0 <= digits.length <= 4
digits[i]是范围['2', '9']的一个数字。
解法一:回溯(推荐)
这是个“所有组合”问题,很自然地会想到用回溯。
从第 0 个数字开始,看它能对应哪些候选字母,把其中一个字母接到路径末尾,向下一位递归。
所有位都处理完,当前路径就是一个可能的字母组合,加入结果列表。
然后撤销刚才的选择(把那个字母从路径里拿掉),换下一个候选字母继续试。
复杂度
- 时间:
O(3^m * 4^n)(组合数:其中 m 个数字对应3 个字母,n 个数字对应4 个字母)
- 空间:
O(k)递归栈+ 当前路径缓存, 其中k是数字串digits的长度 - 递归栈:最多递归
k层 - 路径数组/字符串:维护当前前缀
path(长度 ≤k)
解法二:BFS
用队列维护当前所有前缀,每读入一位数字 d,把当前队列里的每个前缀都和数字 d代表的每个字母拼接,再加入队列里。
相当于逐位扩展的层序遍历。
处理完所有位时,队列里的就都是这个号码能表示的字母组合。
复杂度
- 时间:
O(3^m * 4^n)(组合数:其中 m 个数字对应3 个字母,n 个数字对应4 个字母)
- 空间:
O(3^m * 4^n),队列存放当前层所有前缀。
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-17-电话号码的字母组合
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 14] 最长公共前缀
下一篇
[Leetcode 18] 四数之和