电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

分析

回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。

可以使用回溯法，通过递归构造一棵二叉树，从而得到所有情形，这道题是不需要回退的，因为没有限制条件，仅仅递归即可。

题解

/*
 * @lc app=leetcode.cn id=17 lang=cpp
 *
 * [17] 电话号码的字母组合
 */

// @lc code=start
class Solution {
 public:
  map<int, string> mp = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
                         {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
                         {'8', "tuv"}, {'9', "wxyz"}};
  string str;    //临时存储答案
  vector<string> ans;   
  vector<string> letterCombinations(string digits) {
      if(digits.size()==0){
          return ans;
      }
    dfs(0,digits);
    return ans;
  }

  void dfs(int n, string digits) {
    if (n == digits.size()) {
      ans.push_back(str);    
      return;
    }
    for (int i = 0; i < mp[digits[n]].size(); i++) {
    str.push_back(mp[digits[n]][i]);
      dfs(n+1,digits);   //进入下一层
      str.pop_back();   //回退最后一种情况,加入其他字母
    }
  }
};
// @lc code=end