原题
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入： "23"
输出： ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解法
思想
dfs就嗯搜 →_→
代码
class Solution {
List<String> ans = new ArrayList<>();
char[] chars;
public List<String> letterCombinations(String digits) {
chars = digits.toCharArray();
if(chars.length == 0) return new ArrayList<String>();
List<Character> list = new ArrayList<>();
dfs(list,0);
return ans;
}
public void dfs(List<Character> list,int index){
if(index == chars.length) {
StringBuilder sb = new StringBuilder();
for(Character c:list){
sb.append(c);
}
ans.add(sb.toString());
return;
}
for(char c:numToChars(chars[index])){
List<Character> copy = new ArrayList<>(list);
copy.add(c);
dfs(copy,index+1);
}
}
public char[] numToChars(char num){
switch(num){
case '2':
return new char[]{'a','b','c'};
case '3':
return new char[]{'d','e','f'};
case '4':
return new char[]{'g','h','i'};
case '5':
return new char[]{'j','k','l'};
case '6':
return new char[]{'m','n','o'};
case '7':
return new char[]{'p','q','r','s'};
case '8':
return new char[]{'t','u','v'};
case '9':
return new char[]{'w','x','y','z'};
}
return new char[]{};
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode17-%e7%94%b5%e8%af%9d%e5%8f%b7%e7%a0%81%e7%9a%84%e5%ad%97%e6%af%8d%e7%bb%84%e5%90%88/
相关推荐
-
用一个栈实现另一个栈的排序
原题（来源牛客网） 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？ 解法 ...
-
leetcode752-打开转盘锁
原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由...
-
剑指offer59-队列的最大值
原题（来源Leetcode） 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度...
-
leetcode561-数组拆分I
原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, b...
-
leetcode28-实现strStr()
原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从...
-
leetcode198-打家劫舍
原题 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会...
-
leetcode365-水壶问题
原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升...
-
leetcode706-设计哈希映射
原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...
-
剑指offer47-礼物的最大价值
原题（来源Leetcode） 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一...
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...