题目原文：

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

题意分析：

电话机上一个数字按键对应了多个字符，给出一个数字串，给出所有可能的字符串组合。

将对应关系放入map中后，直接深度搜索即可。

解题代码：

//Input:Digit string "23"
//Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
//通过输入的数字，输出可能的字母组合
//遍历所有情况，因为深度不确定，考虑使用递归，进行深度搜索

#include <iostream>
#include <vector>
#include <map>
using namespace std;


class Solution {
public:
	map<char,string> num2Str;
	char *pstr;
	vector<string> vecBack;
	vector<string> letterCombinations(string digits) {
		vecInit(num2Str);
		vecBack.clear();
		pstr = (char*)malloc((1+digits.length())*sizeof(char));
		if (pstr == NULL)
		{
			return vecBack;
		}
		if (digits.length()>0)
		{
			PushLetter(digits,0);
		}
		
		return vecBack;
	}


	void PushLetter(string digits, int Loc)
	{
		char szNum = digits[Loc];
		string szPoss = num2Str[szNum];

		for (int i=0; i<szPoss.length(); i++)
		{
			pstr[Loc] = szPoss[i];
			if (Loc+1 < digits.length())
			{
				PushLetter(digits,Loc+1);
			}
			else if (Loc+1 == digits.length())
			{
				pstr[Loc+1] = '\0';
				string sRet = pstr;
				vecBack.push_back(sRet);
			}
		}
	}


	//初始化map中的对象
	void vecInit(map<char,string> &vecInput)
	{
		vecInput.insert(make_pair('1',"@"));
		vecInput.insert(make_pair('2',"abc"));
		vecInput.insert(make_pair('3',"def"));
		vecInput.insert(make_pair('4',"ghi"));
		vecInput.insert(make_pair('5',"jkl"));
		vecInput.insert(make_pair('6',"mno"));
		vecInput.insert(make_pair('7',"pqrs"));
		vecInput.insert(make_pair('8',"tuv"));
		vecInput.insert(make_pair('9',"wxyz"));
		vecInput.insert(make_pair('0',"_"));
		vecInput.insert(make_pair('*',"+"));
		//vecInput.insert(make_pair(''))
	}
};