安装iis8 添加网站,宜城网站建设哪家好,51推广平台,华为手机WordPress题目 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。 示例 1#xff1a; 输入#xff1a;digits “2…题目 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 示例 2 输入digits “” 输出[] 示例 3 输入digits “2” 输出[“a”,“b”,“c”] 来源力扣 17. 电话号码的字母组合 思路注意事项
与之前组合不同的地方在于这个题是不同集合组合的回溯。 纯代码
class Solution {
private:string tmp;vectorstring ans;string s[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};void backtracking (string digits, int index){if (digits.size() index){ans.push_back(tmp);return;}string digit s[digits[index] - 0];for (int i 0; i digit.size(); i ){tmp.push_back(digit[i]);backtracking (digits, index 1);tmp.pop_back();}}
public:vectorstring letterCombinations(string digits) {if (digits.size() 0) return ans;backtracking (digits, 0);return ans;}
};题解加注释
class Solution {
private:string tmp; // 存储当前正在构建的字母组合即叶子节点vectorstring ans; // 存储所有字母组合的结果即答案string s[10] // 数字到字母的映射表{, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};// 回溯函数void backtracking(string digits, int index) {// 如果当前组合的长度等于 digits 的长度说明找到一个有效的组合if (digits.size() index) {ans.push_back(tmp); // 将当前组合加入结果集return;}// 获取当前数字对应的字母集合string digit s[digits[index] - 0];// 遍历当前数字对应的所有字母for (int i 0; i digit.size(); i) {tmp.push_back(digit[i]); // 将当前字母加入组合backtracking(digits, index 1); // 递归处理下一个数字tmp.pop_back(); // 回溯移除当前字母}}public:// 主函数生成所有字母组合vectorstring letterCombinations(string digits) {if (digits.size() 0) return ans; // 如果输入为空直接返回空结果backtracking(digits, 0); // 从第 0 个数字开始回溯return ans; // 返回所有字母组合}
};
