问题：

按照手机拨号输入英文字母，给定一串手机拨号数字，求可输入的英文字串的所有可能性。

 

 

Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:
Input: digits = ""
Output: []

Example 3:
Input: digits = "2"
Output: ["a","b","c"]
 
Constraints:
0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

　　

解法：Backtracking（回溯算法）

参数：

• path：到目前为止的数字构成的字母串。
• optionlists：当前数字digits[0]，可选择的字母。

处理：

• 退出条件：if(optionlists的当前数字digits[0]=="") 则将path加入res，return
• for所有可选项：    //'a'+(当前数字digits[0]-'2')*3+（0，1，2）（当前数字为：2～7）+ 1（当前数字为8，9）<由于7和9分别可选4个字母，其他可选3个字母>
  • 做选择：path+=opt
  • 递归：backtracking(path, digits+1<下一个数字>)
  • 撤销选择：path.pop_back()

代码参考：

 1 class Solution {
 2 public:
 3     //'a'+(x-2)*3+（0，1，2）
 4     vector<string> letterCombinations(string digits) {
 5         vector<string> res;
 6         string path;
 7         backtracking(res, path, digits);
 8         return res;
 9     }
10     void backtracking(vector<string>& res, string path, string digits) {
11         int n = 3;
12         if(digits=="") {
13             if(path!="") res.push_back(path);
14             return;
15         }
16         if(digits[0]=='9'||digits[0]=='7') n = 4;
17         for(int i = 0; i < n; i++) {
18             char opt = 'a' + (digits[0] - '2') * 3 + i;
19             if(digits[0]>'7') opt++;
20             path += opt;
21             backtracking(res, path, string(digits.begin()+1, digits.end()));
22             path.pop_back();
23         }
24         return;
25     }
26 };