LeetCode高频题17：电话号码的字母组合

组合"/>

LeetCode高频题17：电话号码的字母组合

LeetCode高频题17：电话号码的字母组合

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

文章目录

• LeetCode高频题17：电话号码的字母组合
• • @[TOC](文章目录)
• 题目
• 一、审题
• 就暴力组合
• 如果你是用字符串类型来接path，那中途就需要恢复现场，探索别的字符串做排头的可能性
• 总结

题目

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

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

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、审题

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：

输入：digits = “”
输出：[]
示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

就暴力组合

比如按2
按3
2代表abc
3代表def
则每一个2和3的字母，组合就行，没啥特别的

电话号盘的字符集：打表

给你个字符串digits
你最终收集的答案每一个组合的长度肯定和digits一样长

所以，就深度优先遍历，让所有digits对应的字符串，从0位置开始，每一个i数字，对应的某一个字符做一次开头，将这个字符放入path[i]，下一个i+1位置就是另一个数字，它对应的某一个字符给path[i+1]

比如：digits=23
i=0处是2，path[0]=a或者b或者c，轮番来做一次排头
i+1=1处是3，path[1]=d或者e或者f，轮番做一次

当i来到digits的N=2位置，就说明成功了一个path，放入结果ans即可
然后探索别的字符开头的情况，直接覆盖path的i位置字符即可。
path如果用数组表示，可以直接覆盖，不需要恢复现场

但是path如果用list装，就需要恢复现场

手撕代码：

        //复习//2--9对应的字符表public static char[][] phone = {{},//0不对应{},//1不对应{'a', 'b', 'c'},//2内部的字符{'d', 'e', 'f'},//3内部的字符{'g', 'h', 'i'},//4内部的字符{'j', 'k', 'l'},//5内部的字符{'m', 'n', 'o'},//6内部的字符{'p', 'q', 'r', 's'},//7内部的字符{'t', 'u', 'v'},//8内部的字符{'w', 'x', 'y', 'z'},//9内部的字符};//所以，就**深度优先遍历**，让所有digits对应的字符串，从0位置开始，每一个字符做一次开头，来组合出一个答案path，//当i来到digits的N位置，就说明成功了一个，放入结果ans即可//定义递归函数f//从digits的字符数组i=0位置出发，找对应的电话表盘//沿途结果放入path，当i到了digits的N位置，path放入ans，返回//再考虑下一个i位置的字符，应该是下一个数字的哪个字符？public static void f(char[] str, int i, char[] path, List<String> ans) {//基本条件就是i来到str的末尾，str就是给定的digits的字符数组，比如'2''3'if (i == str.length) ans.add(String.valueOf(path));//由于是数组，所以不需要清楚现场else {//否则只能走别的路//拿到2这个做一次开头，3做一次开头char[] ch = phone[str[i] - '0'];//01其实不对应的，从2开始应该，找到那行字符数组for(char cc : ch){//每一个可能的字符都要来一次，path被覆盖了，不是列表，所以不需要恢复现场，//每一个数字对应字符数组的字符，做一次开头path[i] = cc;//把当前i数字的其中一个字符拿给path，做i位置的字符f(str, i + 1, path, ans);//接着拼接下一个数字的某个字符来}}}//主函数调用方法：public List<String> letterCombinationsReview(String digits) {if (digitspareTo("") == 0 || digits.length() == 0) return new ArrayList<>();//空//准备中途用的path，结果ansList<String> ans = new ArrayList<>();char[] path = new char[digits.length()];//数字多长，path就有多长//从i这个数字决定，谁拼path，直到所有位置都拼好char[] str = digits.toCharArray();f(str, 0, path, ans);return ans;}

测试：

    public static void test(){Solution solution = new Solution();List<String> res = solution.letterCombinations("23");for(String s:res) System.out.println(s);System.out.println();res = solution.letterCombinationsReview("23");for(String s:res) System.out.println(s);}public static void main(String[] args) {test();}

ad
ae
af
bd
be
bf
cd
ce
cf

问题不大
LeetCode测试：


足够牛逼！

如果你是用字符串类型来接path，那中途就需要恢复现场，探索别的字符串做排头的可能性

这就是排列组合的经典之处：
比如下图
23
从path=ad算计第一个
你下次应该是ae了吧，那请你先把d废了
一样的先废掉e，下次组合出af
再把f废掉，回去把a废掉，探索b开头的可能性
然后裁员bd,be,bf……

class Solution {//复习//2--9对应的字符表public static char[][] phone = {{},//0不对应{},//1不对应{'a', 'b', 'c'},//2内部的字符{'d', 'e', 'f'},//3内部的字符{'g', 'h', 'i'},//4内部的字符{'j', 'k', 'l'},//5内部的字符{'m', 'n', 'o'},//6内部的字符{'p', 'q', 'r', 's'},//7内部的字符{'t', 'u', 'v'},//8内部的字符{'w', 'x', 'y', 'z'},//9内部的字符};//需要恢复现场的代码：//定义递归函数f//从digits的字符数组i=0位置出发，找对应的电话表盘//沿途结果放入path，当i到了digits的N位置，path放入ans，返回//再考虑下一个i位置的字符，应该是下一个数字的哪个字符？public static void f2(char[] str, int i, String path, List<String> ans) {//基本条件就是i来到str的末尾，str就是给定的digits的字符数组，比如'2''3'if (i == str.length) ans.add(path);else {//否则只能走别的路//拿到2这个做一次开头，3做一次开头char[] ch = phone[str[i] - '0'];//01其实不对应的，从2开始应该，找到那行字符数组for(char cc : ch){//每一个可能的字符都要来一次，path被覆盖了，不是列表，所以不需要恢复现场，//每一个数字对应字符数组的字符，做一次开头path += String.valueOf(cc);//把当前i数字的其中一个字符拿给path，拼f2(str, i + 1, path, ans);//接着拼接下一个数字的某个字符来//由于是list,需要恢复现场path = path.substring(0, i);//除掉i}}}//主函数调用方法：public List<String> letterCombinations(String digits) {if (digitspareTo("") == 0 || digits.length() == 0) return new ArrayList<>();//空//准备中途用的path，结果ansList<String> ans = new ArrayList<>();String path = "";//数字多长，path就有多长//从i这个数字决定，谁拼path，直到所有位置都拼好char[] str = digits.toCharArray();f2(str, 0, path, ans);return ans;}
}

总结

提示：重要经验：

1）要注意的是，path如果用数组表示，每次覆盖i位置就行，不用恢复现场，如果是list就需要恢复现场，让path干掉屁股那个字符，探索别的可能性
2）对于数字来说，每个位置i，可能有不同的字符，那就打表准备phone，直接根据i数字去换算下标就行str[i]-‘0’，找到相应位置的对应字符数组，然后这些字符都可以来做一次排头，放入path的i位置
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。