题目描述
给出一个仅包含数字的字符串,给出所有可能的字母组合。
数字到字母的映射方式如下:(就像电话上数字和字母的映射一样)
Input:Digit string "23"Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].注意:虽然上述答案是按字典序排列的,但你的答案可以按任意的顺序给出
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.
思路:使用深度遍历
class Solution { public: vector<string> letterCombinations(string digits) { vector<string> dict{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> res; int n = digits.size(); string out; DFS(digits,0,dict,out,res); return res; } void DFS(string digits,int level, vector<string> dict,string &out, vector<string> &res) { if(level == digits.size()) res.push_back(out); else { string s = dict[digits[level]-'0']; for(int i = 0;i<s.size();++i) { out.push_back(s[i]); DFS(digits,level+1,dict,out,res); out.pop_back(); } } } };