Leetcode 电话号码的字母组合
class Solution {
public:
vector<string> result;
vector<string> phone;
string temp;
Solution (){
phone.push_back("");
phone.push_back("");
phone.push_back("abc");
phone.push_back("def");
phone.push_back("ghi");
phone.push_back("jkl");
phone.push_back("mno");
phone.push_back("pqrs");
phone.push_back("tuv");
phone.push_back("wxyz");
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0) return result;
DFS(0,digits); // 深度优先算法
return result;
}
void DFS(int pos,string digits){
if(pos==digits.size()){ // 结束条件
result.push_back(temp);
return;
}
int num=digits[pos]-'0';
for(int i=0;i<phone[num].size();i++){
temp += phone[num][i];
DFS(pos+1,digits);
temp.erase(pos,1); // 还原
}
}
};