给出一个仅包含数字的字符串,给出所有可能的字母组合。
数字到字母的映射方式如下:(就像电话上数字和字母的映射一样)
Input:Digit string "23"Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].注意:虽然上述答案是按字典序排列的,但你的答案可以按任意的顺序给出
Input:Digit string "23"Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].注意:虽然上述答案是按字典序排列的,但你的答案可以按任意的顺序给出
"23"
["ad","ae","af","bd","be","bf","cd","ce","cf"]
class Solution { public: unordered_map<char,string>mp={{'2',"abc"},{'3',"def"},{'4',"ghi"}, {'5',"jkl"},{'6',"mno"},{'7',"pqrs"}, {'8',"tuv"},{'9',"wxyz"}}; vector<string> letterCombinations(string digits) { vector<string>res={""}; for(auto c:digits){ int sz = res.size(); for(int i =0;i<sz;i++) for(auto t:mp[c]) res.push_back(res[i]+t); res.erase(res.begin(),res.begin()+sz); } return res; } };
* * 牛客网:回溯法 */ ArrayList<String> res=new ArrayList<String>(); public ArrayList<String> letterCombinations(String digits) { if(digits==null||digits.length()==0){ res.add(""); return res; } String[] mapping={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; letterCombinations(digits,0,"",mapping); return res; } private void letterCombinations(String digits, int i, String string,String[] mapping) { if(i>=digits.length()){ res.add(string); return; } String strs=mapping[Character.getNumericValue(digits.charAt(i))]; for(char c:strs.toCharArray()){ letterCombinations(digits,i+1,string+c,mapping); } }
class Solution { private: map<char,string> mp={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}}; vector<string> res; string temp; public: void combine(string &digits,int start){//回溯法 if(start==digits.size()){ res.push_back(temp);return; } for(int i=0;i<mp[digits[start]].size();i++){ temp+=mp[digits[start]][i]; combine(digits,start+1); temp.pop_back(); } } vector<string> letterCombinations(string digits) { combine(digits,0); return res; } };
//dfs
public ArrayList<String> letterCombinations(String digits) {
ArrayList<String> res = new ArrayList<String>();
res.add("");
if(digits ==null||digits.length()==0) return res;
HashMap<Character,String> map =new HashMap<Character, String>();
map.put('1',"1");
map.put('2',"abc");
map.put('3',"def");
map.put('4',"ghi");
map.put('5',"jkl");
map.put('6',"mno");
map.put('7',"pqrs");
map.put('8',"tuv");
map.put('9',"wxyz");
map.put('*',"*");
map.put('0',"0");
map.put('#',"#");
return generate(res,digits,map);
}
public ArrayList<String> generate(ArrayList<String> res,String digits,HashMap<Character,String> map){
if(digits ==null||digits.length()==0){
return res;
}
ArrayList<String> list =new ArrayList<String>();
for(int i=0;i<res.size();i++){
String str =map.get(digits.charAt(0));
for(int j=0;j<str.length();j++)
list.add(res.get(i)+str.charAt(j));
}
res =new ArrayList<String>(list);
list =generate(res, digits.substring(1),map);
return list;
}
class Solution { public: string mp[12]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; vector<string> letterCombinations(string digits) { vector<string> ans(1,""); for(int i=0;i<digits.size();i++){ vector<string> tmp; for(int j=0;j<ans.size();j++) for(int k=0;k<mp[digits[i]-'0'].size();k++) tmp.push_back(ans[j]+mp[digits[i]-'0'][k]); ans=tmp; } return ans; } };
class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res(1,""); int len = digits.size(); if(len==0) return res; const string charMap[10] = {"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; for(int i=0;i<len;i++) { vector<string> temp; int num = digits[i]-'0'; if(num<0 || num>9) break; string letter = charMap[num]; for(int j=0;j<letter.length();j++) { for(int k=0;k<res.size();k++) temp.push_back(res[k]+letter[j]); } swap(res,temp); } sort(res.begin(),res.end()); return res; } };
枚举递归 class Solution { public: vector<string> res; string tmp; map<int, string> num2alp = {{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9,"wxyz"}}; vector<string> letterCombinations(string digits) { if(digits.empty()){ res.push_back(tmp); return res; } else getStr(digits, 0, tmp); return res; } void getStr(string digits, int idx, string tmp){ if(idx == digits.size()) res.push_back(tmp); int im = digits[idx] - '0'; for(int i = 0; i < num2alp[im].size(); ++i){ getStr(digits, idx + 1, tmp + num2alp[im][i]); } } };
/** * * @param digits string字符串 * @return string字符串一维数组 */ function letterCombinations( digits ) { // write code here let phone = { 2: ['a', 'b', 'c'], 3: ['d', 'e', 'f'], 4: ['g', 'h', 'i'], 5: ['j', 'k', 'l'], 6: ['m', 'n', 'o'], 7: ['p', 'q', 'r', 's'], 8: ['t', 'u', 'v'], 9: ['w', 'x', 'y', 'z'], } let res = []; function backtrack(combination, next_digits){ if(next_digits.length === 0){//如果数字串为空,则将当前字母组合插入到res res.push(combination); } else{ for(let letter of phone[next_digits[0]]){//从数字串第一个数字开始循环处理 backtrack(combination + letter, next_digits.substring(1));//将第一个数字的字母组合分别插入combination,再递归处理去掉首个数字剩下的数字串 } } } if(digits){ backtrack('', digits);//回溯函数入口 }else{ return [""]; } return res; } module.exports = { letterCombinations : letterCombinations };
class Solution: def letterCombinations(self , digits ): # write code here worddict = {'2':'abc','3':'def','4':'ghi','5':'jkl', '6':'mno','7':'pqrs','8':'tuv','9':'wxyz'} digits = list(digits) res = [''] for digit in digits: if digit in worddict: word = worddict[digit] l = len(word) n = len(res) #先对res扩容,再按顺序填充 res = res*l for i in range(l): for j in range(n): res[i*n+j] = res[i*n+j] + word[i] return sorted(res)
/* * 目的:给出所有可能的字母组合 * 方法:回溯法 */ void solve(string digits, int pos, string cur, map<int,string>&m, vector<string>&res){ if (pos== digits.size()){ res.push_back(cur); return; } for (int i = 0; i<m[digits[pos]-'0'].size();++i){ solve(digits,pos+1,cur+m[digits[pos]-'0'][i],m,res); } } vector<string> letterCombinations(string digits) { vector<string>res; map<int,string>m; m[2]="abc"; m[3]="def"; m[4]="ghi"; m[5]="jkl"; m[6]="mno"; m[7]="pqrs"; m[8]="tuv"; m[9]="wxyz"; solve(digits, 0, "",m, res); return res; }
class Solution {
public:
map<char,string> co={{'0',""},{'1',""},{'2',"abc"},{'3',"def"},{'4',"ghi"},
{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
vector<string> out;
void core(string s,string res,int idx,int l)
{
if(idx==l)
{
out.push_back(res);
return;
}
string s1=co[s[idx]];
for(int i=0;i<s1.length();i++)
core(s,res+s1[i],idx+1,l);
if(s1.empty())
core(s,res,idx+1,l);
}
vector<string> letterCombinations(string digits)
{
out.clear();
int l=digits.length();
string res="";
if(l>0)
core(digits,res,0,l);
else
out.push_back(res);
return out;
}
};
class Solution { public: vector<string> letterCombinations(string digits) { string n2w[12] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; vector<string> result(1,""); for(int i=0;i<digits.size();i++) { vector<string> temp; for(int j=0;j<result.size();j++) { int num = digits[i] - '0'; for(int k=0;k<n2w[num].size();k++) temp.push_back(result[j]+n2w[num][k]); } result = temp; } return result; } };
回溯法:http://blog.csdn.net/versencoder/article/details/52071930 public class Solution { List<String> result=new ArrayList<String>(); public List<String> letterCombinations(String digits) { if(digits.length()==0) return result; for(int i=0;i<digits.length();i++){ if(digits.charAt(i)>'9'||digits.charAt(i)<'2') return result; } String[] str={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; backtracking(str,digits,new StringBuilder(),0,digits.length()); return result; } public void backtracking(String[] str,String digits,StringBuilder sb,int start,int k){ if(k<0) return ; else if(k==0) { result.add(sb.toString()); //sb=new StringBuilder(); } else{ for(int i=start;i<digits.length();i++){ String s=str[digits.charAt(i)-50]; for(int j=0;j<s.length();j++){ sb.append(s.charAt(j)); backtracking(str,digits,sb,i+1,k-1); sb.deleteCharAt(sb.length()-1); } } } } }
import java.util.*; public class Solution { public String dicMap[]={"abc","def","ghi", "jkl","mno","pqrs", "tuv","wxyz"}; public ArrayList<String> resultList=new ArrayList<String>(); /* * @param digits string字符串 * @return string字符串ArrayList */ public ArrayList<String> letterCombinations (String digits) { // write code here char chArr[]=new char[digits.length()]; place(0,chArr,digits); return resultList; } public void place(int index, char chArr[],String digits ){ if(index==chArr.length){ StringBuilder resultBuilder=new StringBuilder(); for(int i=0;i<chArr.length;i++){ resultBuilder.append(chArr[i]); } resultList.add(resultBuilder.toString()); }else{ Integer curDigit=digits.charAt(index)-'0'; int curDigitIndex=curDigit-2; String allMayCharStr=dicMap[curDigitIndex]; for(int i=0;i<allMayCharStr.length();i++){ char ch=allMayCharStr.charAt(i); chArr[index]=ch; place(index+1,chArr,digits); } } } } 递归回溯法
ArrayList<String> res =new ArrayList<String>(); String[] map={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; public ArrayList<String> letterCombinations (String digits) { // write code here int size = digits.length(); if(size<=0) { res.add(digits); return res; } StringBuffer sb= new StringBuffer(); helper(digits,0,sb); return res; } void helper(String digits,int index,StringBuffer sb) { if(index>=digits.length()) { res.add(sb.toString()); return; } int s = (int)digits.charAt(index)-'0'; for(int i=0;i<map[s].length();i++) { sb.append(map[s].charAt(i)); helper(digits,index+1,sb); sb=sb.deleteCharAt(sb.length()-1); } }
private char[][] chs = { { ' ' }, {}, { 'a', 'b', 'c' }, { 'd', 'e', 'f' }, { 'g', 'h', 'i' }, { 'j', 'k', 'l' }, { 'm', 'n', 'o' }, { 'p', 'q', 'r', 's' }, { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' } }; public ArrayList<String> letterCombinations(String digits) { // write code here if (digits == null) return null; ArrayList<String> list = new ArrayList<>(); list.add(""); for (int i = 0; i < digits.length(); ++i) { list = work(list, digits.charAt(i) - '0'); } return list; } private ArrayList<String> work(ArrayList<String> list, int k) { ArrayList<String> ret = new ArrayList<>(); for (int i = 0; i < list.size(); ++i) { for (int j = 0; j < chs[k].length; ++j) { ret.add(list.get(i) + chs[k][j]); } } return ret; }
private char[][] chs = { { ' ' }, {}, { 'a', 'b', 'c' }, { 'd', 'e', 'f' }, { 'g', 'h', 'i' }, { 'j', 'k', 'l' }, { 'm', 'n', 'o' }, { 'p', 'q', 'r', 's' }, { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' } }; public ArrayList<String> letterCombinations(String digits) { // write code here if (digits == null) return null; ArrayList<StringBuilder> list = new ArrayList<>(); list.add(new StringBuilder()); for (int i = 0; i < digits.length(); ++i) { list = work(list, digits.charAt(i) - '0'); } ArrayList<String> ret = new ArrayList<>(); list.forEach(e -> ret.add(e.toString())); return ret; } private ArrayList<StringBuilder> work(ArrayList<StringBuilder> list, int k) { ArrayList<StringBuilder> ret = new ArrayList<>(); for (int i = 0; i < list.size(); ++i) { for (int j = 0; j < chs[k].length; ++j) { StringBuilder tmp = new StringBuilder(list.get(i)); ret.add(tmp.append(chs[k][j])); } } return ret; }
class Solution: # 回溯 def letterCombinations(self , digits): # write code here string = [] allString = [] pattern = {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"} length = len(digits) def combine(numIndex): if numIndex == length: allString.append("".join(string)) return for s in pattern[digits[numIndex]]: string.append(s) combine(numIndex+1) string.pop() combine(0) return allString