LeetCode 17. Letter Combinations of a Phone Number

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”].

解析：
手机键盘上每个数字对应不同的字符，给定一组数字的字符串，返回他们表示个所有字符情况。
思路：
首先建立数字和字符之间的对应关系，采用回溯方法，比如给定字符23，2对应的字符为“a,b,c”，3对应的字符为“d,e,f”。先处理2表示的每个字符，比如给定a,分别组合3表示的字符可以组合成”ad,ae,af”，然后删除a,处理b,组合形成”bd,be,bf”。依次类推，这里采用递归的方式来处理。
[cc lang=”C ++”]
class Solution {
public:
void helper(vector &char_map, int idx, string &result, string &digits, vector &result_list)
{
if(idx == digits.length())//找到一种字符方案
{
if(result.length() > 0)
{
result_list.push_back(result);
}
}else
{
int index = digits.at(idx)-‘0’;//字符转数值
string candidates = char_map[index];//数字对应的候选字符
for(int index =0; index < candidates.length(); index ++) //遍历每一个候选字符 { result.push_back(candidates[index]); helper(char_map, idx+1, result, digits, result_list);//处理后面一位数字 result.erase(result.length()-1, 1); //回溯 } } } vector letterCombinations(string digits) {
vector result_list;
vector char_map = {” “, ” “, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz”};//建立数字和字符之间的对应关系
string result_str = “”;
helper(char_map, 0, result_str, digits, result_list);
return result_list;
}

};
[/cc]