Leetcode -- Letter Combinations of a Phone Number

Solution 04/02/2014: recursion:

class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     int n = digits.length();  
     static unordered_map<char, string> map{  
      {'2', "abc"},  
      {'3', "def"},  
      {'4', "ghi"},  
      {'5', "jkl"},  
      {'6', "mno"},  
      {'7', "pqrs"},  
      {'8', "tuv"},  
      {'9', "wxyz"}  
     };  
     std::vector<string> ret;  
     if(n <= 0) {  
       ret.emplace_back("");  
       return ret;  
     } else if(n == 1) {  
       if(map.count(digits[0]) > 0) {  
         for(char c: map[digits[0]]) {  
           ret.emplace_back(string(1,c));  
         }  
       }  
     } else {  
       char current = digits[n - 1];  
       vector<string> rest(letterCombinations(digits.substr(0, n - 1)));  
       if(map.count(current) > 0) {  
         for(char c : map[current]) {  
           for(string s: rest) {  
             string temp;  
             temp += s+ c;  
             ret.emplace_back(temp);  
           }  
         }  
       }  
     }  
     return ret;  
   }  
 };  

Iterative

 class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     int n = digits.length();  
     static unordered_map<char, string> map{  
      {'2', "abc"},  
      {'3', "def"},  
      {'4', "ghi"},  
      {'5', "jkl"},  
      {'6', "mno"},  
      {'7', "pqrs"},  
      {'8', "tuv"},  
      {'9', "wxyz"}  
     };  
     std::vector<string> ret{""};  
     for(int i = 0; i < n; ++i) {  
       if(map.count(digits[i]) > 0) {  
         vector<string> newVec;  
         for(auto& item : ret) {  
           for(char c : map[digits[i]]) {  
             string temp(item + c);  
             newVec.emplace_back(temp);  
           }  
         }  
         swap(ret, newVec);  
       }  
     }  
     return ret;  
   }  
 };