給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。
示例 1：
輸入：digits = “23”
輸出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
輸入：digits = “”
輸出：[]
示例 3：
輸入：digits = “2”
輸出：[“a”,“b”,“c”]
提示：
0<= digits.length<= 4
digits[i] 是范圍 [‘2’, ‘9’] 的一個數(shù)字。
該方法較好理解
如例子“23”
先將2對應(yīng)的a，b，c加入隊列，然后每次將a pop出隊列時，將a分別與3對應(yīng)的def分別組合加入隊列。
代碼如下：
重慶分公司
重慶分公司
class Solution {public:
vectorletterCombinations(string digits)
{vectorres;
string s[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
queueq;
int n=digits.size();
for(int i=0;iif(q.empty())
{for(int j=0;jwhile(q.front().size()for(int j=0;jstring e=q.front()+s[digits[i]-'0'].substr(j,1);
q.push(e);
}
q.pop();
}
}
}
while(!q.empty())
{res.push_back(q.front());
q.pop();
}
return res;
}
}; 這個方法可能較為難理解
回溯其實可以理解為多條路分別走，你選擇進(jìn)入函數(shù)即走下一步，不進(jìn)入函數(shù)往下走就是換個方向走，還沒到下一步。
這里講一講回朔法的思路：1這一步要干嘛，2下一步要干嘛，3目的是什么
使用回溯法最好要能畫成n叉樹的結(jié)構(gòu)，樹的寬度就用for循環(huán)，深度就用遞歸。
另外回溯法要注意進(jìn)入下一層遞歸時某些值才改變，可以在調(diào)用自身的括號中改變，不能在調(diào)用前面改變
如果不能在括號中改變，可以這樣
for(int i=idx;iif(candidates[i]>target-sum) continue;
if(candidates[i]<=target-sum)
{v.push_back(candidates[i]);
function(target,sum+candidates[i],candidates,v,i);
v.pop_back();
}
} push之后再pop這樣就不會對后面for循環(huán)操作造成影響
另外，在同一層的回溯數(shù)據(jù)是不變的，但是二維數(shù)組傳進(jìn)去就可以積累答案，因為后面對一維數(shù)組有回溯操作，所以保證數(shù)據(jù)不變，而對結(jié)果數(shù)組沒有，所以結(jié)果數(shù)組可以積累。
注意如果要可以積累的話，要傳入地址?。。。。。。。。?br />int也是，如果傳入的是固定的值，就可以不用傳入地址。
然后這一題配一張圖更好理解
首先第一步是把第一個數(shù)字的字符加進(jìn)去，第二步是把第二個數(shù)字的字符加進(jìn)去，目的是將字符相加并放入數(shù)組中
故可以用函數(shù)加字符，同時這里每一個數(shù)字都要回溯，故還有用for循環(huán)
class Solution {public:
string s[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vectorres;
void v(string digits,string ss,int idx)
{ if(idx==digits.size()) res.push_back(ss);
else
{ string x=s[digits[idx]-'0'];
for(int i=0;iletterCombinations(string digits)
{if(digits.size()==0) return res;
v(digits,"",0);
return res;
}
}; 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
