首页 > 代码库 > Leetcode-Letter Combinations of a Phone Number
Leetcode-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"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
采用dfs深度搜索.
1 #include <iostream> 2 #include <map> 3 #include <vector> 4 #include <string> 5 6 class Solution{ 7 private: 8 map<char,vector<char> > dict; 9 vector<string> res;10 public:11 void createDict()12 {13 dict.clear();14 dict[‘2‘].push_back(‘a‘);15 dict[‘2‘].push_back(‘b‘);16 dict[‘2‘].push_back(‘c‘);17 dict[‘3‘].push_back(‘d‘);18 dict[‘3‘].push_back(‘e‘);19 dict[‘3‘].push_back(‘f‘);20 dict[‘4‘].push_back(‘g‘);21 dict[‘4‘].push_back(‘h‘);22 dict[‘4‘].push_back(‘i‘);23 dict[‘5‘].push_back(‘j‘);24 dict[‘5‘].push_back(‘k‘);25 dict[‘5‘].push_back(‘l‘);26 dict[‘6‘].push_back(‘m‘);27 dict[‘6‘].push_back(‘n‘);28 dict[‘6‘].push_back(‘o‘);29 dict[‘7‘].push_back(‘p‘);30 dict[‘7‘].push_back(‘q‘);31 dict[‘7‘].push_back(‘r‘);32 dict[‘7‘].push_back(‘s‘);33 dict[‘8‘].push_back(‘t‘);34 dict[‘8‘].push_back(‘u‘);35 dict[‘8‘].push_back(‘v‘);36 dict[‘9‘].push_back(‘w‘);37 dict[‘9‘].push_back(‘x‘);38 dict[‘9‘].push_back(‘y‘);39 dict[‘9‘].push_back(‘z‘);40 }41 42 void dfs(int dep,int maxDep,string &s,string ans){43 if(dep==maxDep){44 res.push_back(ans);45 return;46 }47 48 for(int i=0;i<dict[s[dep]].size();i++){49 dfs(dep+1,maxDep,s,ans+dict[s[dep]][i]);50 }51 }52 53 vector<string> letterCombinations(string digits){54 res.clear();55 createDict();56 dfs(0,digits.size(),digits,"");57 }58 59 };
Leetcode-Letter Combinations of a Phone Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。