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”]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
同样，是利用dfs。 深搜复杂度O(3^n)，空间复杂度O(n);
注意对字符串常量数组map的初始化方法【放在本地可能过不了得拿数组转】 此外将n和digits设置为全局的方式简直治愈~
class Solution { public: const vector<string> map {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; int n; string digits; vector<string> letterCombinations(string digits) { this->n=digits.size(); this->digits=digits; vector<string> result; if(n==0) return result; string temp=""; generate(temp,0,0,result); return result; } void generate(string temp,int step,int size,vector<string>& result){ if(step==n){ result.push_back(temp); return; } //从step位置开始遍历 for(int i=size;i<n;i++){ for(int j=0;j<map[digits[i]-'0'].size();j++){ string pre=temp; temp=temp+map[digits[i]-'0'][j]; generate(temp,step+1,i+1,result); temp=pre; } } } };