如果您对Leetcode17.LetterCombinationsofaPhoneNumber感兴趣，那么这篇文章一定是您不可错过的。我们将详细讲解Leetcode17.LetterCombinati
如果您对Leetcode 17. 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(bfs)、17. Letter Combinations of a Phone Number（电话号码的字母组合）、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(bfs)
- 17. Letter Combinations of a Phone Number（电话号码的字母组合）
- Leetcode - 017. Letter Combinations of a Phone Number
Leetcode 17. Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
class Solution {
public:
string mapping[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void get_string(string &digits,int l,vector<string> &ans,string &x){
if(l==digits.size()){
ans.push_back(x);
return;
}
for(auto &e:mapping[digits[l]-''2'']){
x.push_back(e);
get_string(digits,l+1,ans,x);
x.pop_back();
}
}
vector<string> letterCombinations(string digits) {
/*
注意考虑digits空的情况。
*/
vector<string> ans;
if(digits.empty()) return ans;
string x;
get_string(digits,x);
return ans;
}
};
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 }
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，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
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的分享就到这里，希望大家有所收获，若想了解更多关于17. Letter Combinations of a Phone Number、17. Letter Combinations of a Phone Number(bfs)、17. Letter Combinations of a Phone Number（电话号码的字母组合）、Leetcode - 017. Letter Combinations of a Phone Number等相关知识，可以在本站进行查询。
本文标签：
