在这篇文章中，我们将为您详细介绍17.LetterCombinationsofaPhoneNumber的内容，并且讨论关于电话号码的字母组合的相关问题。此外，我们还会涉及一些关于17.LetterCo
在这篇文章中，我们将为您详细介绍17. Letter Combinations of a Phone Number的内容，并且讨论关于电话号码的字母组合的相关问题。此外，我们还会涉及一些关于17. Letter Combinations of a Phone Number、17. Letter Combinations of a Phone Number(bfs)、Leetcode - 017. Letter Combinations of a Phone Number、leetcode 17 Letter Combinations of a Phone Number的知识，以帮助您更全面地了解这个主题。
本文目录一览：- 17. Letter Combinations of a Phone Number（电话号码的字母组合）（电话号码对应的字母组合）
- 17. Letter Combinations of a Phone Number
- 17. Letter Combinations of a Phone Number(bfs)
- Leetcode - 017. Letter Combinations of a Phone Number
- leetcode 17 Letter Combinations of a Phone Number
17. Letter Combinations of a Phone Number（电话号码的字母组合）（电话号码对应的字母组合）
Given a string containing digits from 2-9 inclusive,return all possible letter combinations that the number Could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"].
Note:
Although the above answer is in lexicographical order,your answer Could be in any order you want.
方法一：递归
import java.util.ArrayList; import java.util.List; class Solution { public List<String> letterCombinations(String digits) { List<String> result=new ArrayList<String>(); //存结果 String[] map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; char[]tmp=new char[digits.length()]; if(digits.length()<1) return result; rec(digits,0,tmp,map,result); return result; } private void rec(String digits,int index,char[] tmp,String[] map,List<String> result) { if(index==digits.length()){ result.add(new String(tmp)); return; } char tmpChar=digits.charat(index); for(int i=0;i< map[tmpChar - ‘0‘].length();i++){ tmp[index]=map[tmpChar-‘0‘].charat(i); rec(digits,index+1,result); } } }
方法二：回溯
import java.util.ArrayList; import java.util.List; class Solution { public List<String> letterCombinations(String digits) { List<String> result=new ArrayList<String>(); //存结果 String[] map={"","wxyz"}; StringBuilder tmp=new StringBuilder(); if(digits.length()<1) return result; backtrack(digits,result); return result; } private void backtrack(String digits,StringBuilder tmp,List<String> result) { if(index==digits.length()){ result.add(new String(tmp)); return; } char tmpChar=digits.charat(index); for(int i=0;i< map[tmpChar - ‘0‘].length();i++){ tmp.append(map[tmpChar-‘0‘].charat(i)); backtrack(digits,result); tmp.deleteCharat(tmp.length()-1); } } }
总结：
递归是一种数据结构，是函数中调用本身来解决问题。
回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了。
回溯搜索是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
17. Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<String>();
if(digits == null || digits.length() == 0){
return result;
}
Map<Character, char[]> map = new HashMap<Character, char[]>();
map.put(''2'', new char[]{''a'', ''b'', ''c''});
map.put(''3'', new char[]{''d'', ''e'', ''f''});
map.put(''4'', new char[]{''g'', ''h'', ''i''});
map.put(''5'', new char[]{''j'', ''k'', ''l''});
map.put(''6'', new char[]{''m'', ''n'', ''o''});
map.put(''7'', new char[]{''p'', ''q'', ''r'', ''s''});
map.put(''8'', new char[]{''t'', ''u'', ''v''});
map.put(''9'', new char[]{''w'', ''x'', ''y'', ''z''});
StringBuilder sb = new StringBuilder();
dfs(digits, sb, map, result);
return result;
}
public void dfs(String digits, StringBuilder sb, Map<Character, char[]> map, List<String> result){
if(sb.length() == digits.length()){
result.add(sb.toString());
return;
}
for(char c : map.get(digits.charAt(sb.length()))){ //利用sb.length()查到当前到了第几位
sb.append(c);
dfs(digits, sb, map, result);
sb.deleteCharAt(sb.length() - 1);
}
}
}
17. Letter Combinations of a Phone Number(bfs)
2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
1 class Solution {
2 public List<String> letterCombinations(String digits) {
3 LinkedList<String> res = new LinkedList<String>();
4 if(digits.isEmpty()) return res;
5 String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
6 res.add("");
7 for(int i=0;i<digits.length();i++){
8 int x=Character.getNumericValue(digits.charAt(i));
9 while(res.peek().length()==i){
10 String t = res.remove();
11 for (char s :mapping[x].toCharArray())
12 res.add(t+s);
13 }
14 }
15 return res;
16 }
17 }
Leetcode - 017. Letter Combinations of a Phone Number
原题地址
我的思路：
一个字符对应多种选择，需要遍历整个状态空间才能得到所求的ans，满足 dfs + backtracing组合求解模式。
1.每个char对应的可能性是确定的，map用来优化time cost
2.当前解的状态应该用 & ，虽然不使用 & 在本题也可以AC，出于backtracing 优化space cost的考虑，应该使用 &
3.dfs + backtring 的一般性套路即为：
3.1 在dfs中优先判断当前解是否为可行解
3.2 剪枝，pass明显不是解的状态空间
3.3 对于当前状态的所有可能的下行状态，用for循环，每次遵循(1.加入状态 2.dfs 3.撤回状态)即可完成dfs + backtraing的套路性求解
更多参考启发
class Solution {
public:
map<int,string> mmp
{{''2'',"abc"},{''3'',"def"},{''4'',"ghi"},{''5'',"jkl"},
{''6'',"mno"},{''7'',"pqrs"},{''8'',"tuv"},{''9'',"wxyz"}};
void dfs(vector<string> & vct,string &curans,string cur)
{
if(cur == "")
{
vct.push_back(curans);
return;
}
string s = mmp[cur[0]];
cur = cur.substr(1);
for(int i = 0;i< s.length();++i)
{
curans += s[i];
dfs(vct,curans,cur);
curans = curans.substr(0,curans.length() - 1);
}
}
vector<string> letterCombinations(string digits) {
vector<string> vct;
string s = "";
if(digits.length() <= 0)
return vct;
dfs(vct,s,digits);
return vct;
}
};
leetcode 17 Letter Combinations of a Phone Number
题目详情
Given a digit string, return all possible letter combinations that the number could represent.
mapping of digit to letters (just like on the telephone buttons) is given below.这道题要求我们给出，对于输入的按键组合，我们需要返回按键所对应的所有可能的字符串。而按键和字母的对应关系如上图。
想法
- 这道题就是一种排列组合，对于一种按键组合我们要按照输入顺序排列组合出所有的字符串。
- 每一次按键我们都会得到一系列字符串，如"2"得到"a","b","c"。这将成为下一次操作的前序字符串。
- 我们将字符串存储在linkedlist里面，通过peek操作依次取出前序字符串。对于每一个不同的前序字符串，我们都要在其后面分别加上当前键所表示的不同字符，再将获得的结果字符串加入linkedlist里面。
解法
public List<String> letterCombinations(String digits) {
LinkedList<String> res = new LinkedList<String>();
if(digits.length() == 0){
return res;
}
String[] mapping = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
res.add("");
for(int i=0;i<digits.length();i++){
int index = Character.getNumericValue(digits.charAt(i));
while(res.peek().length() == i){
String temp = res.remove();
for(char c : mapping[index].toCharArray()){
res.add(temp+c);
}
}
}
return res;
}今天关于17. Letter Combinations of a Phone Number和电话号码的字母组合的讲解已经结束，谢谢您的阅读，如果想了解更多关于17. Letter Combinations of a Phone Number、17. Letter Combinations of a Phone Number(bfs)、Leetcode - 017. Letter Combinations of a Phone Number、leetcode 17 Letter Combinations of a Phone Number的相关知识，请在本站搜索。
本文标签：
