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.

 

BFS:

1 class Solution { 2 public: 3     vector
      
        letterCombinations(string digits) 4     { 5         vector
       
         vs = {
    "", "", "abc", "def","ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; 6         vector
        
          result; 7         result.push_back(""); 8         if(digits.empty()) return {}; 9         for (size_t i = 0; i < digits.size(); ++i) {10             vector
         
           qc;11             string strtmp(vs[digits[i]-'0']);12             for (size_t j = 0; j < strtmp.size(); ++j) {13                 for (size_t k = 0; k < result.size(); ++k) {14                     qc.push_back(result[k] + strtmp[j]);15                 }16             }17             result = qc;18         }19         return result;20     }21 };
         
        
       
      

2% 3ms

对于含有0和1的项,比如"123",程序运行结果不符合预期.但是却通过OJ,所以此题有待严谨.

 

BFS:

 

 

class Solution {public:    vector
     
       letterCombinations(string digits)    {        vector
      
        vs = {
   "", "", "abc", "def","ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };        vector
       
         result;        result.push_back("");        if(digits.empty()) return {};        for (size_t i = 0; i < digits.size(); ++i) {            vector
        
          qc;            string strtmp(vs[digits[i]-'0']);            for (size_t j = 0; j < strtmp.size(); ++j) {                for (size_t k = 0; k < result.size(); ++k) {                    qc.push_back(result[k] + strtmp[j]);                }            }            result.swap(qc);//swap does not take memory copy         }        return result;    }};
        
       
      
     

the method thought by  

65.33% 0ms

 

backtrackiing:

class Solution { //by luming.zhang.75(Creater) redace85(Modifier) public:    vector
     
       letterCombinations(string digits) {        vector
      
        ret;        if(0>=digits.size()) return ret;            const string map[]={
   "0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};        backTrackingFun(map,digits,"",ret);            return ret;    }        void backTrackingFun(const string m[], const string &digits, string r, vector
       
         &ret){        int c=r.size();        if(digits.size()==c){            ret.push_back(r);            return;        }            auto str = m[digits.at(c)-48]; // '0' = 48        for(auto it=str.cbegin();it!=str.cend();++it){            r.push_back(*it);            backTrackingFun(m,digits,r,ret);            r.pop_back();        }    }};
       
      
     

 

r size:0aar size:1dadr size:2r pop back:deaer size:2r pop back:efafr size:2r pop back:fr pop back:abbr size:1dbdr size:2r pop back:deber size:2r pop back:efbfr size:2r pop back:fr pop back:bccr size:1dcdr size:2r pop back:decer size:2r pop back:efcfr size:2r pop back:fr pop back:cadaeafbdbebfcdcecf

 

2% 3ms