https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

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.

---

• 字符串组合 + FIFO queue
• 两种解法，一种用到queue，另一种用vector模拟queue使用。注意初始化比较tricky的地方。
• queue - C++ Reference
  • http://www.cplusplus.com/reference/queue/queue/
• vector::swap - C++ Reference
  • http://www.cplusplus.com/reference/vector/vector/swap/

1 //  2 //  main.cpp  3 //  LeetCode  4 //  5 //  Created by Hao on 2017/3/16.  6 //  Copyright © 2017年 Hao. All rights reserved.  7 //  8 //  9 //  main.cpp 10 //  LeetCode 11 // 12 //  Created by Hao on 2017/3/16. 13 //  Copyright © 2017年 Hao. All rights reserved. 14 // 15 #include 
      
        16 #include 
       
         17 #include 
        
          18 #include 
         
           19 using namespace std; 20  21 class Solution { 22 public: 23     vector
          
            letterCombinations(string digits) { 24         vector
           
             vResult; 25 26 if (digits.empty()) return vResult; 27 28 vector
            
              dict{ "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 29 30 queue
             
               myQueue; 31 myQueue.push(""); // Tricky step for the initial value 32 33 for (int i = 0; i < digits.size(); i ++) { 34 int n = myQueue.size(); 35 string sTemp; 36 37 for (int j = 0; j < n; j ++) { 38 // retrieve old letter 39 sTemp = myQueue.front(); 40 myQueue.pop(); 41 42 // append new letter 43 for (auto & ch : dict[digits.at(i) - '0']) 44 myQueue.push(sTemp + ch); 45 } 46 } 47 48 while (! myQueue.empty()) { 49 vResult.push_back(myQueue.front()); 50 myQueue.pop(); 51 } 52 53 return vResult; 54 } 55 56 vector
              
                letterCombinations2(string digits) { 57 vector
               
                 vResult; 58 59 if (digits.empty()) return vResult; 60 61 vector
                
                  dict{ "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 62 63 vResult.push_back(""); // Tricky step for the initial value 64 65 for (int i = 0; i < digits.size(); i ++) { 66 vector
                 
                   vTemp; // temp result to override the initial value "" 67 string sTemp; 68 69 for (int j = 0; j < vResult.size(); j ++) { 70 sTemp = vResult[j]; 71 72 for (auto & ch : dict[digits.at(i) - '0']) 73 vTemp.push_back(sTemp + ch); 74 } 75 76 vResult.swap(vTemp); // update result iteratively 77 } 78 79 return vResult; 80 } 81 }; 82 83 int main(int argc, char* argv[]) 84 { 85 Solution mySolution; 86 87 vector
                  
                    inputs { "", "23"}; 88 vector
                   
                     outputs; 89 90 /* 91 92 ad ae af bd be bf cd ce cf 93 */ 94 for (auto & input : inputs) { 95 outputs = mySolution.letterCombinations(input); 96 97 for (auto & output : outputs) { 98 cout << output << " "; 99 }100 cout << endl;101 102 outputs = mySolution.letterCombinations2(input);103 104 for (auto & output : outputs) {105 cout << output << " ";106 }107 cout << endl;108 }109 110 return 0;111 }