手机网站建设技术方案,wordpress 添加搜索,素材网站都有哪些,国家企业信用信息网文章目录 17. 电话号码的字母组合回溯算法 17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。
示例… 文章目录 17. 电话号码的字母组合回溯算法 17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例 1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 示例 2 输入digits “” 输出[] 示例 3 输入digits “2” 输出[“a”,“b”,“c”] 提示
0 digits.length 4digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
回溯算法
class Solution {
public:// 主函数接受一个数字字符串返回可能的字母组合。vectorstring letterCombinations(string digits) {// 如果输入的字符串为空则直接返回空的结果集。if (digits.size() 0) {return result;}// 开始回溯过程从第0个字符开始。backstracking(digits, 0);// 返回最终的字母组合结果集。return result;}private:// 用来存储最终的字母组合结果。vectorstring result;// 用作路径记录记录当前的字母组合。string path;// 映射数组index对应的字符串表示电话按键上数字所代表的所有字母。// 注意0和1并不对应任何字母故留空。string a[10] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};// 回溯函数s为输入的数字字符串index为当前处理的层级索引。void backstracking(string s, int index) {// 如果路径字符串的长度和数字字符串的长度相同说明找到了一个完整的字母组合。if (path.size() s.size()) {// 将当前路径添加到结果集中。result.push_back(path);return;}// 获取当前数字字符对应的所有可能字母。string b a[s[index] - 0];// 遍历这些字母。for (int i 0; i b.size(); i) {// 将当前字母加到路径中。path.push_back(b[i]);// 递归调用回溯函数处理下一个数字字符。backstracking(s, index 1);// 回溯移除路径末尾的字母以尝试下一个可能字母。path.pop_back();}// 当前分支处理完毕返回上一级。return;}
};
代码中使用了回溯算法的模板这是求解排列组合类问题的常用方法。函数backstracking是核心它会递归地探索所有可能的字母组合每次递归调用都会向一个组合中添加一个字母直到得到一个完整的字母组合然后将其添加到结果集中。函数中使用了path变量来存储当前的字母组合状态并在每次递归返回之前进行回溯以便尝试下一个可能的字母组合。
请注意代码中使用的变量result和path是私有成员它们在多次调用回溯函数时保持状态。变量a是一个映射数组它将数字映射到对应的所有可能字母上。这种映射正是根据电话按键布局定义的。
