17. Letter Combinations of a Phone Number
Description
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.
Analysis
此题利用回溯法解决较为简洁。利用一个整形数组完成从键盘上的数字到键盘上的字符串的一个映射。
回溯函数中的整型变量tmp用于计算digits字符串中当前字符相对于'a'的偏移量，再减去2是因为map数组的索引是从0开始的，对于digits中的元素,其相对于'a'的偏移量应先减去2，其对应的字符串才是该元素对应的真正的在键盘上的字符串。
之后的迭代过程中，每次递归调用时，start的值应该+1，而不是常见的i+1，因为根据此题的要求，在固定了第一个数字对应的字符串中的某个字符后，下一个字符应该从下一个数字对应的字符串中的字符中去取。
例如:此题中的23,其combination中的第一个字符串的第一个元素来自于2，第二个元素来自于3.
代码如下:
code
class Solution {
private:
void backtracking(vector<string> & result,string & temp,string & digits,int start,int * map){
if(start==digits.size()){
result.push_back(temp);
return;
}
int tmp=digits[start]-'0'-2;
for(int i=map[tmp];i<map[tmp+1];++i){
temp.push_back('a'+i);
backtracking(result,temp,digits,start+1,map);
temp.pop_back();
}
return;
}
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
string temp="";
int map[10]={0,3,6,9,12,15,19,22,26};
backtracking(result,temp,digits,0,map);
return result;
}
};