[Leetcode] 17. Letter Combinations of a Phone Number
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"].
采用递归的方式。
class Solution { public: //建立词典 0 1 2 3 4 5 6 7 8 9 vector<string> dict{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; vector<string> letterCombinations(string digits) { vector<string> res; if(digits.size()==0) return res; help(digits, 0, string(""), res); return res; } //pos:当前数字的索引，pre：之前已经建立的字符串，res：保存的结果 void help(string digits,int pos,string pre, vector<string>& res) { if(pos==digits.size())//digits遍历完成，保存结果 { res.push_back(pre); return; } int num = digits[pos]-'0'; for(int i=0;i<dict[num].size();i++) { string cur = pre+dict[num][i]; help(digits, pos+1, cur, res); } } };