LeetCode 17. Letter Combinations of a Phone Number

  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 <iostream>
 16 #include <string>
 17 #include <vector>
 18 #include <queue>
 19 using namespace std;
 20 
 21 class Solution {
 22 public:
 23     vector<string> letterCombinations(string digits) {
 24         vector<string>  vResult;
 25         
 26         if (digits.empty()) return vResult;
 27         
 28         vector<string> dict{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
 29         
 30         queue<string> 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<string> letterCombinations2(string digits) {
 57         vector<string> vResult;
 58         
 59         if (digits.empty()) return vResult;
 60         
 61         vector<string> 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<string> 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<string>  inputs {"", "23"};
 88     vector<string>  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 }