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.

思路：

穷举法加回溯。用一个二维数组保存每个数字对应可能出现的字母，当每一层穷举完后回溯到上一层，再次穷举下个字符可能出现的组合。

1 static char keys[8][4] = {
   {
   'a', 'b', 'c'},       // 2 2                          {
   'd', 'e', 'f'},       // 3 3                          {
   'g', 'h', 'i'},       // 4 4                          {
   'j', 'k', 'l'},       // 5 5                          {
   'm', 'n', 'o'},       // 6 6                          {
   'p', 'q', 'r', 's'},  // 7 7                          {
   't', 'u', 'v'},       // 8 8                          {
   'w', 'x', 'y', 'z'}}; // 9 9 static int sizes[] = {
   3, 3, 3, 3, 3, 4, 3, 4}; 10 11 class Solution {12 public:13     vector
     
       letterCombinations(string digits) {14         vector
      
        result;15         int levels = digits.size(), current_level = 0;16         vector
       
         indexes(levels, 0);17         18         if (0 == levels) {19             return vector
        
         (1, "");20         }21         22         while (true) {23             int ch_index = digits[current_level] - '0' - 2;24             25             if (sizes[ch_index] == indexes[current_level]) {26                 if (0 == current_level) {27                     break;28                 }29                 30                 indexes[current_level] = 0;31                 --current_level;32                 ++indexes[current_level];33                 continue;34             }35             else {36                 if (current_level < (levels - 1)) {37                     ++current_level;38                 }39                 else {40                     string s;41                     int i;42                     43                     for (i = 0; i < current_level; ++i) {44                         s.push_back(keys[digits[i] - '0' - 2][indexes[i]]);45                     }46                     s.push_back('?');47                     48                     for (i = 0; i < sizes[ch_index]; ++i) {49                         s[current_level] = keys[ch_index][i];50                         result.push_back(s);51                     }52                     53                     indexes[current_level] = sizes[ch_index];54                 }55             }56         }57         58         return result;59     }60 };