编辑距离计算函数需正确初始化二维DP数组：dpi=i、dp0=j，循环从1开始，状态转移分字符相等、替换、插入/删除三种情况；应避免递归实现，优先使用迭代并做空间优化。
编辑距离计算函数怎么写才不出错
编辑距离（Levenshtein Distance）是单词纠错的核心，但手写时容易在边界处理和索引偏移上出错。常见错误是二维 DP 数组初始化不对，或循环从 1 开始却忘了 dp[i][0] 和 dp[0][j] 的含义。
正确做法是：用 dp[i][j] 表示 s1.substr(0, i) 变成 s2.substr(0, j) 的最小操作数，初始化 dp[i][0] = i、dp[0][j] = j，内层循环从 1 开始，状态转移分三种情况：
- 字符相等：
dp[i][j] = dp[i-1][j-1] - 替换：
dp[i][j] = dp[i-1][j-1] + 1 - 插入/删除：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
注意：不要用递归+记忆化代替迭代 DP，实际纠错需高频调用，递归栈开销大且易爆栈；也不要省略空间优化——若只关心距离值（不回溯路径），可用一维数组压缩到 O(min(len1, len2)) 空间。
如何快速筛选候选词而不遍历整个词典
直接对每个输入词和词典中所有词计算编辑距离，O(N×M) 复杂度完全不可行（比如 10 万词典 × 每次 100 次查询 = 百万级计算）。必须预过滤。
立即学习“C++免费学习笔记（深入）”；
实用策略是组合使用以下条件（按顺序应用，尽早剪枝）：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 长度差超过最大允许编辑距离（如
max_dist = 2），直接跳过：abs(len(a) - len(b)) > max_dist - 首字母不同（对英文有效）且
max_dist ，可排除（常见拼写错误很少改首字母） - 用前缀树（Trie）按前 2–3 字母索引词典，只查同前缀的子集
- 更进一步：用 n-gram 倒排索引（如 trigram），取输入词的全部 trigram，查交集后再算编辑距离
示例：输入 "recieve"，先取 trigram {"rec", "eci", "civ", "ive"}，查含至少 2 个的候选词，再对这些词算编辑距离。这能将候选集从 10 万压到百量级。
为什么不能只依赖编辑距离排序结果
单纯按编辑距离升序返回 top-k，会漏掉明显更合理的纠错。比如输入 "adn"，"and" 和 "an" 编辑距离都是 1，但后者是截断而非拼写错误；又如 "teh" 到 "the" 是 1，但 "teh" 到 "eh" 也是 1，显然前者更合理。
必须引入语言模型打分，最简方案是加一个频率权重：
- 用公开词频数据（如 Google Ngram 或 COCA）给每个候选词赋
log_freq - 最终得分 =
-edit_distance + 0.5 * log_freq（系数可调） - 避免直接用原始频率——高频词天然有优势，但也要防低频专业词被淹没
另一个易忽略点：大小写。输入 "iPhone" 不该匹配 "iphone" 后再靠编辑距离拉平——应在预处理阶段统一转小写，但保留原始 casing 用于最终输出。
C++ 实现里哪些 STL 容器和算法能真正提速
别默认用 std::vector<:string></:string> 存词典——查找慢、内存碎片多。关键选择如下：
- 词典加载后固定不变？用
std::vector+std::sort+std::lower_bound做二分前缀查找，比 map 快 3–5 倍 - 需要动态增删？用
absl::flat_hash_set（或google::dense_hash_set），比std::unordered_set内存更紧凑、缓存友好 - DP 计算中避免重复构造
std::string子串，传std::string_view（C++17）或 const char* + len - 频繁调用编辑距离？把
dp数组声明为局部静态或复用缓冲区，避免每次 new/delete
最后提醒：编辑距离本身不区分错误类型（比如 "hte" → "the" 是换位，但标准 Levenshtein 当作两次操作）。如果业务中换位错误占比高（如触摸屏输入），得单独加一条「相邻字符交换」转移分支，并设 cost=1，否则纠错准确率会明显下降。
