百度作文网站wordpress添加文章目录

百度作文网站,wordpress添加文章目录,东莞凤岗做网站,加强网络舆情监测一、题目介绍1.1 题目描述给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。数字到字母的映射与电话按键一致#xff08;1 不对应任何字母#xff09;#xff1a;2: abc3: def4: ghi5: jkl6: mno7: pqrs8: tuv9: wxyz1.2…一、题目介绍1.1 题目描述给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。数字到字母的映射与电话按键一致1 不对应任何字母2: abc3: def4: ghi5: jkl6: mno7: pqrs8: tuv9: wxyz1.2 示例示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 2输出[a,b,c]示例 3输入digits 输出[]1.3 题目难度中等1.4 核心考点回溯算法深度优先搜索 DFS的应用字符串的遍历与组合构建递归思想的落地实现二、解题思路2.1 核心思想这是一道典型的组合型回溯问题核心逻辑是为每个数字建立固定的字母映射表递归遍历每个数字对应的字母逐步构建字母组合路径当路径长度等于输入数字的长度时说明已构建完成一个完整组合将其加入结果集回溯过程中复用同一个路径字符串通过覆盖的方式减少内存开销。2.2 算法流程处理边界条件若输入字符串为空直接返回空数组初始化结果数组和路径字符串路径长度与输入数字长度一致递归函数DFS终止条件当前处理到第n个数字所有数字处理完毕将路径加入结果遍历当前数字对应的所有字母将字母填入路径的对应位置递归处理下一个数字最终返回结果数组。三、完整代码实现#include iostream #include vector #include string using namespace std; class Solution { // 数字到字母的映射表索引对应数字0-9 static constexpr string MAPPING[10] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; public: vectorstring letterCombinations(string digits) { int n digits.length(); // 边界条件空字符串直接返回空数组 if (n 0) { return {}; } vectorstring ans; // 存储最终结果 string path(n, 0); // 路径字符串长度固定为n避免频繁拼接 // 递归lambda表达式C14及以上支持this auto auto dfs [](this auto dfs, int i) - void { // 递归终止处理完所有数字 if (i n) { ans.emplace_back(path); // 将当前路径加入结果 return; } // 获取当前数字对应的字母串 const string letters MAPPING[digits[i] - 0]; // 遍历当前数字的所有字母 for (char c : letters) { path[i] c; // 直接覆盖路径的第i位无需拼接/回退 dfs(i 1); // 递归处理下一个数字 } }; dfs(0); // 从第0个数字开始递归 return ans; } }; // 测试函数 void test() { Solution s; // 测试案例1 vectorstring res1 s.letterCombinations(23); cout 输入: 23 | 输出: ; for (const string str : res1) { cout str ; } cout endl; // 测试案例2 vectorstring res2 s.letterCombinations(2); cout 输入: 2 | 输出: ; for (const string str : res2) { cout str ; } cout endl; // 测试案例3 vectorstring res3 s.letterCombinations(); cout 输入: 空 | 输出: (res3.empty() ? 空数组 : 非空) endl; } int main() { test(); return 0; }四、代码深度解析4.1 映射表定义static constexpr string MAPPING[10] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};使用static constexpr定义常量映射表避免每次调用函数时重复创建提升性能索引 0 和 1 对应空字符串因为 0、1 无字母映射索引 2-9 对应电话按键的字母。4.2 边界条件处理if (n 0) { return {}; }输入为空字符串时直接返回空数组符合题目要求。4.3 路径字符串优化string path(n, 0);传统回溯通常使用空字符串逐步拼接再在递归返回时「回退」pop_back此处直接初始化长度为n的路径字符串通过覆盖指定位置的方式构建组合无需回退操作减少字符串拼接 / 删除的开销。4.4 递归 Lambda 表达式auto dfs [](this auto dfs, int i) - void { ... };C14 引入的「泛型 lambda」「this 捕获」实现递归 lambda无需额外定义全局 / 类内递归函数this auto dfs表示 lambda 自身的引用用于递归调用捕获列表[]表示按引用捕获外部变量ans、path、digits、MAPPING。4.5 递归核心逻辑if (i n) { ans.emplace_back(path); return; } for (char c : letters) { path[i] c; dfs(i 1); }终止条件i n表示所有数字处理完毕将当前路径加入结果集遍历当前数字的所有字母将字母填入路径的第i位递归处理下一个数字i1由于路径是覆盖式修改无需手动「回溯」传统回溯的pop_back操作代码更简洁。五、测试结果输入: 23 | 输出: ad ae af bd be bf cd ce cf 输入: 2 | 输出: a b c 输入: 空 | 输出: 空数组完全符合题目预期。六、算法复杂度分析6.1 时间复杂度假设输入数字的长度为n每个数字对应k个字母k∈[3,4]总组合数为3^n或4^n取决于数字对应的字母数时间复杂度O(3^n ~ 4^n)即所有组合的总数。6.2 空间复杂度递归调用栈的深度为n数字长度路径字符串占用O(n)空间结果数组占用O(3^n ~ 4^n)空间存储所有组合总空间复杂度O(3^n ~ 4^n)。七、扩展与优化7.1 非递归迭代实现如果不想使用递归也可以通过迭代的方式实现vectorstring letterCombinations_iter(string digits) { if (digits.empty()) return {}; vectorstring ans {}; for (char d : digits) { vectorstring temp; const string letters MAPPING[d - 0]; for (const string s : ans) { for (char c : letters) { temp.push_back(s c); } } ans.swap(temp); } return ans; }7.2 优化点说明本文的递归实现使用「固定长度路径 覆盖式修改」比传统的「拼接 回退」减少了字符串操作的开销映射表使用static constexpr避免重复初始化提升性能递归 lambda 比单独定义递归函数更简洁代码内聚性更强。八、总结本题是回溯算法的经典入门题核心在于理解「逐步构建组合 递归遍历」的思想。本文提供的实现方案有以下特点代码简洁高效利用 C14 的 lambda 递归简化代码结构路径字符串优化避免频繁拼接和回退操作边界条件处理完善覆盖空输入等特殊情况时间 / 空间复杂度最优符合题目要求。掌握本题的回溯思想后可进一步解决类似的组合问题如组合总和、子集等是算法学习中不可或缺的基础知识点。