17.letter-combinations-of-a-phone-number.md

17.电话号码的字母组合

1. 描述

   • 已知：
     • 与电话按键相同的 数字到字母的映射（ 1不对应任何字母），
     • 一个仅包含数字 2-9 的字符串。
   • 返回所有它能表示的字母组合。

2. 示例:

   • 输入："23"
   • 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
   • 说明:
     • 尽管上面的答案是按字典序排列的，你可以任意选择答案输出的顺序。

3. 实现

   class Solution {
   public:
       vector<string>res;
       string path;
       unordered_map<char, string> digit_character = {
           {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
           {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
       };
   
       void dfs(string digits, int pos ){
           // 结束 条件
           if(pos == digits.size()){
               res.push_back(path);
               return;
           }        
           for(auto c: digit_character[digits[pos]]){
               // 选择
               path.push_back(c);
               // 回溯
               dfs(digits, pos+1);
               // 撤销选择
               path.pop_back();
           }
       }
       
       vector<string> letterCombinations(string digits) {
           if(digits.empty())
               return {};
           dfs(digits, 0);
           return res;
       }
   };