https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

<aside> 💡

本题与前两题组合的差别：

1. 之前的组合是在一个集合中选取元素进行组合，本题是在多个集合中进行组合
2. 本题中多了一步从数字映射到字母的操作

回溯三部曲：

• 参数：
  • map<int, vector<char>> dict：用于将数字映射到字符数组的哈希表
  • vector<string>：存放最终结果的全局变量
  • string path：存放当前路径下组合的字符串（相当于一个一维数组）
  • int num：本次递归从digits[num]开始搜索
  • string& digits：题意中的数字字符串
• 终止条件：
  • 组合中的元素个数等于digits中的元素个数，说明完成组合，将结果进行保存并返回
• 单层逻辑：
  • 获取当前数字的映射数组
  • 节点操作：当前组合（path）中添加当前值（letter[i]）
  • 递归：获取digits中的下一个数字进行组合（递归参数传入num+1）
  • 回溯：letter[i]在该位置的所有组合已经全部收集完成，将letter[i]弹出当前组合 </aside>

map<char, vector<char>> mp;
string cur;
vector<string> ans;

void backtracking(int pos, const string& digits) {
    if (cur.size() == digits.size()) {
        ans.push_back(cur);
    }

    vector<char> dict = mp[digits[pos]];
    for (int i = 0; i < dict.size(); ++i) {
        cur.push_back(dict[i]);
        backtracking(pos + 1, digits);
        cur.pop_back();
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.empty()) {
        return {};
    }
    mp.insert({ '2', {'a', 'b', 'c'}});
    mp.insert({ '3', {'d', 'e', 'f'}});
    mp.insert({ '4', {'g', 'h', 'i'}});
    mp.insert({ '5', {'j', 'k', 'l'}});
    mp.insert({ '6', {'m', 'n', 'o'}});
    mp.insert({ '7', {'p', 'q', 'r', 's'}});
    mp.insert({ '8', {'t', 'u', 'v'}});
    mp.insert({ '9', {'w', 'x', 'y', 'z'}});

    backtracking(0, digits);
    return ans;
}