首页
首页 教程 派聪明
  • 首页
  • 教程
  • 派聪明
  • 登录
登录技术派畅享更多权益

用户名密码登录

其他登录:
icon_GitHubCreated with sketchtool.
绑定星球,畅享VIP服务

微信扫码/长按识别登录

输入验证码
有效期五分钟 👉 手动刷新

登录即同意 用户协议 和 隐私政策

绑定二哥编程星球,畅享 VIP 尊享服务!

戳我了解如何获取星球编号,新窗口打开

添加二哥微信 itwanger 审核更快

记得备注 星球编号
我会根据星球编号进行审核
1
两数之和
更新时间: 2023年12月09日
星球
2
两数相加
更新时间: 2023年12月10日
星球
3
无重复字符的最长子串
更新时间: 2023年12月12日
星球
4
寻找两个正序数组的中位数
更新时间: 2023年12月14日
星球
5
最长回文子串
更新时间: 2023年12月18日
星球
6
Z 字行变换
更新时间: 2023年12月26日
星球
7
整数反转
更新时间: 2023年12月28日
星球
8
字符串转成整数
更新时间: 2024年01月01日
星球
9
回文数
更新时间: 2024年01月03日
星球
10
正则式匹配
更新时间: 2024年01月17日
星球
11
盛最多水的容器
更新时间: 2024年01月20日
星球
12
整数转罗马数字
更新时间: 2024年01月21日
星球
13
罗马数字转整数
更新时间: 2024年01月22日
星球
14
最长公共前缀
更新时间: 2024年01月23日
星球
15
三数之和
更新时间: 2024年01月25日
星球
16
最接近的三数之和
更新时间: 2024年01月27日
星球
17
电话号码的字母组合
更新时间: 2024年01月29日
星球
18
四数之和
更新时间: 2024年01月30日
星球
19
删除链表中的倒数第N个节点
更新时间: 2024年01月31日
星球
20
有效的括号
更新时间: 2024年02月01日
星球
21
合并两个有序链表
更新时间: 2024年02月02日
星球
22
括号生成
更新时间: 2024年02月03日
星球
23
合并K个升序链表
更新时间: 2024年02月04日
星球
24
两两交换链表中的节点
更新时间: 2024年02月06日
星球
25
K个一组翻转链表
更新时间: 2024年02月07日
星球
26
删除有序数组中的重复项
更新时间: 2024年02月11日
星球
27
移除元素
更新时间: 2024年02月14日
星球
28
实现 strStr()
更新时间: 2024年02月19日
星球
29
两数相除
更新时间: 2024年02月22日
星球
30
串联所有单词的子串
更新时间: 2024年02月27日
星球
31
下一个排列
更新时间: 2024年02月29日
星球
32
最长有效括号
更新时间: 2024年05月30日
星球
33
搜索旋转排序数组
更新时间: 2024年06月03日
星球
34
在排序数组中查找元素的头尾位置
更新时间: 2024年06月14日
星球
35
搜索插入位置
更新时间: 2024年06月15日
星球
36
有效的数独
更新时间: 2024年06月16日
星球
37
解数独
更新时间: 2024年08月01日
星球
38
外观数列
更新时间: 2024年08月02日
星球
39
组合总和
更新时间: 2024年08月03日
星球
40
组合总和②
更新时间: 2024年08月04日
星球
41
缺失的第一个整数
更新时间: 2024年08月06日
星球
42
接雨水
更新时间: 2024年08月07日
星球
43
字符串相乘
更新时间: 2024年08月08日
星球
44
通配符匹配
更新时间: 2024年09月04日
星球
45
跳跃游戏
更新时间: 2024年09月06日
星球
46
全排列
更新时间: 2024年09月08日
星球
47
全排列②
更新时间: 2024年09月14日
星球
48
旋转图像
更新时间: 2024年09月18日
星球
49
字母异位词分组
更新时间: 2024年09月20日
星球
50
Pow(x, n)
更新时间: 2024年09月29日
星球
51
N 皇后
更新时间: 2024年11月14日
星球
52
N 皇后②
更新时间: 2024年11月14日
星球
53
最大子数组和
更新时间: 2024年11月16日
星球
54
螺旋矩阵
更新时间: 2024年11月20日
星球
55
跳跃游戏
更新时间: 2024年11月21日
星球
56
合并区间
更新时间: 2025年01月26日
星球
57
插入区间
更新时间: 2025年02月01日
星球
关注公众号
原创
017.电话号码的字母组合——技术派-二哥的 LeetCode 刷题笔记

题意

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

难度

中等

示例

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入:digits = ""
输出:[]

输入:digits = "2"
输出:["a","b","c"]

分析 1

这道题对于新手来说,可能第一时间会比较难消化,但耐着性子思考一下,思路就很清晰了。

比如说 2 对应的是 abc,3 对应的是 def,那么 23 对应的就是 ad、ae、af、bd、be、bf、cd、ce、cf。

也就是一个排列组合。

那我们的思路如下:

①、建立一个数字到字母的映射,比如 2 对应的是 abc,3 对应的是 def,我们用数组来就可以。

// 数字到字母的映射
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

0 和 1 属于占位符,没有对应的字母,因为输入的字符串只包含 2-9 的数字。

②、建立一个队列,我们用LinkedList来实现,初始时队列中只有一个空字符串。

LinkedList<String> combinations = new LinkedList<>();
combinations.add(""); // 初始添加一个空字符串到队列中

空字符串是为了方便后续的处理,否则下面这两个方法就没办法直接使用,要判空,很麻烦。

combinations.peek();
String t = combinations.remove();

③、第一层 for 循环,遍历输入的字符串,比如说 23,遍历 2 和 3,排列组合嘛。

for (int i = 0; i < digits.length(); i++) {
	// ...
}

④、while 循环负责将队列中的字符串取出,并且与上一步中组合过的字母进行组合,比如说输入是 234 的时候,2 与 “” 空字符串组合,结果为 a、b、c,3 与 2 对应的 a、b、c 组合,4 与 23 组合后的 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" 组合。依次类推。

while (combinations.peek().length() == i) {
	String t = combinations.remove();
	// ...
}

peek() 方法用于获取队列的头部元素,但不会移除这个元素,remove() 方法用于获取队列的头部元素,并且移除这个元素,防止重复组合,用过了就删除。

⑤、第二层 for 循环,遍历当前数字对应的所有字母,比如说 2 对应的是 abc,3 对应的是 def。

for (char s : mapping[digit].toCharArray()) {
	// ...
}

来看完整的题解代码:

class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> combinations = new LinkedList<>();
        // 如果输入为空,直接返回空列表
        if (digits == null || digits.length() == 0) {
            return combinations;
        }

        // 数字到字母的映射
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        combinations.add(""); // 初始添加一个空字符串到队列中

        // 遍历每个数字
        for (int i = 0; i < digits.length(); i++) {
            int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字
            // 当队列中的字符串长度与当前处理的数字索引相同时,处理队列中的字符串
            while (combinations.peek().length() == i) {
                String t = combinations.remove(); // 从队列中取出一个字符串
                // 遍历当前数字对应的所有字母
                for (char s : mapping[digit].toCharArray()) {
                    combinations.add(t + s); // 将取出的字符串与当前字母相结合,然后加入队列中
                }
            }
        }
        return combinations; // 返回包含所有组合的列表
    }
}

当输入 digits = "23" 时,我们来模拟一下整个题解过程:

初始化

  • mapping: {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
  • combinations: [""] (初始时只包含一个空字符串)

迭代过程

①、处理数字 '2'(对应 "abc")

  • 从 combinations 中取出 "" (队列现在为空)
  • 将 "" 与 "abc" 中的每个字符结合
  • 新的组合: ["a", "b", "c"] 加入到队列

③、处理数字 '3'(对应 "def")

  • 从 combinat

已加入二哥编程星球,即刻绑定星球编号解锁🔐

该文档仅「二哥编程星球」的VIP用户可见

二哥的编程星球内容包括:

1. 付费文档: 技术派、MYDB 等项目配套的 120+篇教程查看权限

2. 面试指南: 校招、社招的 40 万+字面试求职攻略

3. 智能助手: 无限期使用派聪明 AI 助手,已对接讯飞星火和 ChatGPT双通道,不用花 1 分钱

4. 专属问答: 向二哥 1v1 发起提问,内容不限于 offer 选择、学习路线、职业规划等

5. 简历修改: 提供简历修改服务,附赠星球 100+优质简历模板可供参考

6. 学习环境: 打造一个沉浸式的学习环境,有一种高考冲刺、大学考研的氛围


二哥的星球

》步骤①:微信扫描上方二维码,点击「加入知识星球」按钮

》步骤②:访问星球置顶帖球友必看: https://t.zsxq.com/11rEo9Pdu,获取项目配套文档的语雀访问地址和密码

已加入星球,绑定星球编号
删除提醒

确定删除《017.电话号码的字母组合——技术派-二哥的 LeetCode 刷题笔记》吗

真诚点赞 诚不我欺

回复