Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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) {
        
                   // 1 2      3     4     5     6     7      8     9 
         string d[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
         vector<string> v({""});
        if(digits.empty()) return  vector<string>();
         for(int i = 0; i < digits.size(); ++ i)
         {
             vector<string> temp;
             for(int j = 0; j < v.size(); ++ j)
                 for(int k = 0; k < d[digits[i] - '0'].size(); ++ k)
                     temp.push_back(v[j] + d[digits[i] - '0'][k]);
             v = temp;
        }
         return v;
    }
};

我自己做了相关的测试，并且记录了执行过程：

#include <iostream>
#include<vector>
#include<string>
using namespace std;
vector<string> letterCombinations(string digits) {
        
                   // 1 2      3     4     5     6     7      8     9 
         string d[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
         vector<string> v({""});
        if(digits.empty()) return  vector<string>();
         for(int i = 0; i < digits.size(); ++ i)
         {
             vector<string> temp;
             for(int j = 0; j < v.size(); ++ j)
                 for(int k = 0; k < d[digits[i] - '0'].size(); ++ k)
				 {temp.push_back(v[j] + d[digits[i] - '0'][k]);cout<<"v[j]="<<v[j]<<endl<<"d[digits[i] - '0'][k]="<<d[digits[i] - '0'][k]<<endl;}
             v = temp;
        }
         return v;
    }
int main()
{
	vector<string>::iterator it;
	vector<string> t;
	t=letterCombinations("23");
	for(it=t.begin();it!=t.end();it++)
   cout << *it<<endl;
   return 0;
}

v[j]=
d[digits[i] - '0'][k]=a
v[j]=
d[digits[i] - '0'][k]=b
v[j]=
d[digits[i] - '0'][k]=c
v[j]=a
d[digits[i] - '0'][k]=d
v[j]=a
d[digits[i] - '0'][k]=e
v[j]=a
d[digits[i] - '0'][k]=f
v[j]=b
d[digits[i] - '0'][k]=d
v[j]=b
d[digits[i] - '0'][k]=e
v[j]=b
d[digits[i] - '0'][k]=f
v[j]=c
d[digits[i] - '0'][k]=d
v[j]=c
d[digits[i] - '0'][k]=e
v[j]=c
d[digits[i] - '0'][k]=f
ad
ae
af
bd
be
bf
cd
ce
cf