Letter Combinations of a Phone Number

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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.

代码：

 class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     if (digits.empty()) return {};  
     vector<string> mapping = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     string s;  
     vector<string> result;  
     letterCombinationsHelper(digits, mapping, s, result);  
     return result;  
   }  
     
   void letterCombinationsHelper(const string& digits, vector<string>& mapping, string& s, vector<string> &result) {  
     if (s.size() == digits.size()) {  
       result.push_back(s);  
       return;  
     }  
     string &letters = mapping[digits[s.size()] - '2'];   
     for (int i = 0; i < letters.size(); ++i) {  
       s.push_back(letters[i]);  
       letterCombinationsHelper(digits, mapping, s, result);  
       s.pop_back();  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   vector<string> letterCombinations(string digits) {  
     string mapping[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     vector<string> res;  
     if (digits.empty()) return {};  
     for (int i = 0; i < digits.size(); ++i) {  
       vector<string> tmp;  
       auto& letters = mapping[digits[i] - '2'];  
       for (int j = 0; j < letters.size(); ++j) {  
         if (res.empty()) {  
           string s(1, letters[j]);  
           tmp.push_back(s);   
           continue;  
         }  
         for (int k = 0; k < res.size(); ++k) {  
           tmp.push_back(res[k] + letters[j]);  
         }  
       }  
       res = move(tmp);  
     }  
     return res;  
   }  
 };