給定一個(gè)僅包含數(shù)字 2-9 的字符串活喊,返回所有它能表示的字母組合搜囱。
給出數(shù)字到字母的映射如下(與電話按鍵相同)以舒。注意 1 不對應(yīng)任何字母霎肯。
輸入:"23"
輸出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
這種求解排列組合的問題擎颖,看到組合的字眼第一反應(yīng)就是回溯法(實(shí)際就是DFS榛斯、迭代)÷酰或者用隊(duì)列去做(實(shí)際上是BFS)驮俗,也可以多叉樹的問題。代碼如下:注意回溯迭代的參數(shù)問題:
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if(!digits.size()) return res;
map<int,string> tel;
tel.insert(pair<int,string>(2,"abc"));
tel.insert(pair<int,string>(3,"def"));
tel.insert(pair<int,string>(4,"ghi"));
tel.insert(pair<int,string>(5,"jkl"));
tel.insert(pair<int,string>(6,"mno"));
tel.insert(pair<int,string>(7,"pqrs"));
tel.insert(pair<int,string>(8,"tuv"));
tel.insert(pair<int,string>(9,"wxyz"));
string tmp = "";
int length = digits.size();
push_it(res,length,tel,digits,0,tmp);
return res;
}
private:
void push_it(vector<string> &res,int length,map<int,string> tel,string digits,int j,string tmp){
if(j==length){
res.push_back(tmp);
tmp = "";
j = 0;
return;
}
for(int i=0;i<tel[digits[j]-'0'].size();i++){
tmp+=tel[digits[j]-'0'].substr(i,1);
push_it(res,length,tel,digits,j+1,tmp);
tmp= tmp.substr(0,tmp.size()-1);
}
return;
}
};