[数据结构与算法]LeetCode 17.电话号码的字母组合 回溯法 C/C++

题目连接
题解参考链接

主要思路：首先用一个字符串数组digitMap[10]存储数字和字母的映射关系；然后设置两个全局变量，一个为vector< string > ans作为最终的返回结果，另一个为string s，表示已有的字母排列（回溯过程中始终维护这个字符串）；该字符串s初始为空，每次取电话号码的一位数字，从digitMap中获得该数字对应的字符串，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。
举例：文字描述繁琐的话，最好是模拟一下就清晰了，例如digits序列为“23”，首先字符串s为空，索引index = 0，指向digits序列的第一个位置即2，然后取出2对应的字符串为abc，然后将a插入s，此时s =“a”，之后回溯，索引index+1，指向digits序列的第二个位置，即3,而3所对应的字符串为def，同样的道理，遍历该字符串def，先将d插入到s中，此时 s=“ad”，索引index+1 = 2，即此时的s为符合条件的一个完整的字母组合，将其放入最终结果ans中，然后返回，接下来运行回溯函数（backtrack()）的下一句语句：s.pop_back()，即回退，把d删除，此时s=“a”，继续循环，下一个字母为e，在插入s中，s=“ae”…如此往复，最终达到最终结果。详见代码。

class Solution {
private:
	const string digitMap[10] = {
		"","","abc","def",
		"ghi","jkl","mno",
		"pqrs","tuv","wxyz"
	};
public:
	vector<string> ans;
	string s;
	void backtrack(const string& digits,int index) {
		if(index==digits.length()){
			ans.push_back(s);
			return ;
		}
		int num = digits[index]-'0';
		string letters = digitMap[num];
		for(int i = 0;i<letters.length();++i) {
			s.push_back(letters[i]);
			backtrack(digits,index+1);
			s.pop_back();

		}
	}
	vector<string> letterCombinations(string digits) {
		if(digits.length()==0)return ans;
		backtrack(digits,0);
		return ans;
	}
};