题目：

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
     
       letterCombinations(string digits) {            vector
      
        ret;            if ( digits.empty() ) return ret;             map
       
         digitLetters;            digitLetters[0] = "";            digitLetters[1] = "";            digitLetters[2] = "abc";            digitLetters[3] = "def";            digitLetters[4] = "ghi";            digitLetters[5] = "jkl";            digitLetters[6] = "mno";            digitLetters[7] = "pqrs";            digitLetters[8] = "tuv";            digitLetters[9] = "wxyz";            vector
        
          letterBegin(10,0);            int index = 0;            string tmp;            Solution::combine(ret, tmp, index, digits, digitLetters, letterBegin);            return ret;    }    static void combine(        vector
         
          & ret,         string& tmp,         int index,         string& digits,         map
          
           & digitLetters, vector
           
            & letterBegin) { if (index==digits.size()) { ret.push_back(tmp); return; } int curr = digits[index]-'0'; string letters = digitLetters[curr]; for ( int i = 0; i < letters.size(); ++i ) { letterBegin[curr] = i; tmp.push_back(letters[i]); Solution::combine(ret, tmp, index+1, digits, digitLetters, letterBegin); tmp.erase(tmp.end()-1); } }};
           
          
         
        
       
      
     

tips：

上述的代码是AC的。思路也就是常规dfs的思路：

1. 终止条件是层级到了digits的长度

2. 每一层递归相当于根据该位置的数字选一个字母

但是，个人感觉这道题的题干要求没说清楚；既然是letter combinations，而不是letter permutation，那么“ac”和“ca”就应该算一个combination，但是OJ之后发现默认“ac”和“ca”算两个。加入“ac”和“ca”算一个，有没有解法呢？代码如下：

class Solution {public:    vector
     
       letterCombinations(string digits) {            vector
      
        ret;            if ( digits.empty() ) return ret;             map
       
         digitLetters;            digitLetters[0] = "";            digitLetters[1] = "";            digitLetters[2] = "abc";            digitLetters[3] = "def";            digitLetters[4] = "ghi";            digitLetters[5] = "jkl";            digitLetters[6] = "mno";            digitLetters[7] = "pqrs";            digitLetters[8] = "tuv";            digitLetters[9] = "wxyz";            vector
        
          letterBegin(10,0);            int index = 0;            string tmp;            Solution::combine(ret, tmp, index, digits, digitLetters, letterBegin);            return ret;    }    static void combine(        vector
         
          & ret,         string& tmp,         int index,         string& digits,         map
          
           & digitLetters, vector
           
            & letterBegin) { if (index==digits.size()) { ret.push_back(tmp); return; } int curr = digits[index]-'0'; string letters = digitLetters[curr]; for ( int i = letterBegin[curr]; i < letters.size(); ++i ) { letterBegin[curr] = i; tmp.push_back(letters[i]); Solution::combine(ret, tmp, index+1, digits, digitLetters, letterBegin); tmp.erase(tmp.end()-1); } }};
           
          
         
        
       
      
     

tips：

多维护一个letterBegin的数组，标记“当前的组合中，某个数字对应的字母序列中应该从第几个字母开始取”。

如果输入是“22”，那么给出的解集就是：

aa

ab

ac

bb

bc

cc

从这个例子可以看出来，算法的原理就是维护某一个数字对应字母序列：如果数字重复出现，那么对应的字母要保证字典序递增，这样就不会用重复的。

可惜题目并不是这么要求的。

===============================================

既然题目要求简单了，则再追求一个迭代的解法。AC的代码如下：

class Solution {public:    vector
     
       letterCombinations(string digits) {            vector
      
        ret;            if (digits.empty()) return ret;            ret.push_back("");            map
       
         digitLetters;            digitLetters[2] = "abc";            digitLetters[3] = "def";            digitLetters[4] = "ghi";            digitLetters[5] = "jkl";            digitLetters[6] = "mno";            digitLetters[7] = "pqrs";            digitLetters[8] = "tuv";            digitLetters[9] = "wxyz";            for ( size_t i = 0; i < digits.size(); ++i )            {                int curr = digits[i]-'0';                string letters = digitLetters.find(curr)==digitLetters.end() ? "" : digitLetters[curr];                vector
        
          tmp = ret;                ret.clear();                for ( size_t j = 0; j < tmp.size(); ++j )                {                    for ( size_t k = 0; k < letters.size(); ++k )                    {                        string ori = tmp[j];                        ori += letters[k];                        ret.push_back(ori);                    }                }            }            return ret;    }};
        
       
      
     

完毕。

======================================

第二次过这道题，用dfs过的。注意如果原来的digits==""返回的也是空。

class Solution {public:        vector
     
       letterCombinations(string digits)        {                map
      
        digit_letters;            digit_letters['2'] = "abc";            digit_letters['3'] = "def";            digit_letters['4'] = "ghi";            digit_letters['5'] = "jkl";            digit_letters['6'] = "mno";            digit_letters['7'] = "pqrs";            digit_letters['8'] = "tuv";            digit_letters['9'] = "wxyz";            vector
       
         ret;            if ( digits=="" ) return ret;            vector
        
          tmp;            Solution::dfs(ret, digits, tmp, digit_letters);             return ret;        }        static void dfs(            vector
         
          & ret,             string digits,             vector
          
           & tmp, map
           
            & digit_letters) { if ( tmp.size()==digits.size() ) { ret.push_back(string(tmp.begin(),tmp.end())); return; } int index = tmp.size(); for ( int i=0; i