题目描述

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

给出一个数字串，确定所有可能的字符串，数字对应的字符如图中手机键盘所示，不要求顺序。

题目解析

第一个想法是使用类似带进位的数字串表示，不过感觉有点麻烦。 然后想到利用递归，第i位字符自身的循环嵌套i+1位字符的循环。

letterloop(digits,i){ for(第i位){ letterloop(digits,i+1); } }

然后想一下有什么是要传递下去的。

之后看了标签是backtracking回溯法，恍然大悟，原来就是不需要判断的回溯法，走完所有分支的深度遍历。

代码

class Solution { public: vector<string> dig={" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//建立“数字-字符”表； vector<string> letterCombinations(string digits) { vector<string> ans_vec;//答案集合 string ans_str(digits.size(),' ');//候选答案 letteriter(ans_vec,digits,ans_str,0); return ans_vec; } //需要将候选答案传到下一层 void letteriter(vector<string>&ans_vec, const string &digits, string &ans_str, int n){ if(digits.size()==0) return; if(n==digits.size())//在叶子节点保存候选答案，返回 { ans_vec.push_back(ans_str); return; } int d = digits[n]-'0'; for(auto it:dig[d]) { ans_str[n]=it; letteriter(ans_vec,digits,ans_str,n+1); } return; } };