电话号码的字母组合解题思路和代码示例

题目描述

解题思路

代码示例


class Solution
{
public:vector<string> letterCombinations(string digits) {vector<string> combinations;//用来存放组合结果的解集if (digits.empty()) //如果输入为空&＃xff0c;直接返回{return combinations;}unordered_map<char, string> phoneMap//建立哈希表{{&＃39;2&＃39;, "abc"},{&＃39;3&＃39;, "def"},{&＃39;4&＃39;, "ghi"},{&＃39;5&＃39;, "jkl"},{&＃39;6&＃39;, "mno"},{&＃39;7&＃39;, "pqrs"},{&＃39;8&＃39;, "tuv"},{&＃39;9&＃39;, "wxyz"}};string combination;//存放部分解backtrack(combinations, phoneMap, digits, 0, combination);//递归求解return combinations;}void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) //将部分解按地址传入&＃xff0c;避免重复拷贝{if (index &＃61;&＃61; digits.length()) //递归出口{combinations.push_back(combination);//组合好的解插入结果解集中} else {char digit &＃61; digits[index];const string& letters &＃61; phoneMap.at(digit);//at 查找key所对应的值&＃xff0c;如果存在&＃xff1a;返回key对应的值&＃xff0c;可以直接修改&＃xff0c;和[]操作一样。如果不存在&＃xff1a;抛出 out_of_range 异常.for (const char& letter: letters) {combination.push_back(letter);//插入字符backtrack(combinations, phoneMap, digits, index &＃43; 1, combination);//递归combination.pop_back();//将组合完的解从部分解中去除}}}
};

力扣