首页 > 代码库 > 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