编辑距离必须用动态规划实现，递归版因重复子问题和栈溢出不可用；二维dp表时间复杂度o(m×n)，需正确初始化边界，实操推荐先写清二维版再优化。
编辑距离计算必须用动态规划，递归会超时
直接写递归版 edit_distance 看似简洁，但对长度超过 15 的字符串，调用栈爆炸、重复子问题爆炸，实际项目中基本不可用。真正可用的是二维 DP 表实现，时间复杂度 O(m*n)，空间可优化到 O(min(m,n))。
常见错误是忽略边界初始化：第 0 行表示「空字符串 → target[0..j]」，需插入 j+1 次；第 0 列表示「source[0..i] → 空字符串」，需删除 i+1 次。漏掉这个，dp[0][0] 之后全错。
实操建议：
- 用
vector<vector>></vector>初始化(m+1) x (n+1)表，先填满第 0 行/列 - 状态转移只依赖左、上、左上三个格子，可滚动数组优化，但首次实现建议先写清楚二维版
- 若单词平均长度 ≤ 20，直接用
O(m*n)安全；若词典含 10 万词，需后续加剪枝（见下一条）
对大规模词典查纠错词，必须加编辑距离上界剪枝
遍历整个词典逐个算编辑距离，在 10 万词规模下，单次查询耗时轻松破秒——用户输入 “acress” 时不可能等 800ms 才出 “actress”。核心解法是提前终止：当某词的当前编辑距离已超过设定阈值（如 2），立刻跳过。
更高效的是用 Levenshtein automaton 或前缀树（Trie）+ 动态规划联合剪枝，但工程落地首选简单有效的启发式剪枝：
- 先快速排除长度差 > 阈值的候选词（如阈值=2，输入长 6，则只查长度为 4/5/6/7/8 的词）
- DP 过程中，一旦某行最小值 > 阈值，整行可提前 break（利用 DP 表每行单调非减的性质）
- 用
std::priority_queue维护当前 top-K 最小距离，一旦队列满且新距离 ≥ 队首，直接丢弃
构建纠错候选集时，不能只依赖编辑距离数值
编辑距离相同的情况下，“cafe” → “caffe”（少一个 f）和 “cafe” → “case”（替换 e→s）语义合理度差异巨大。纯数字排序会导致拼写错误被低频词挤掉。
真实场景要叠加权重：
- 优先保留原词大小写模式（如输入 “iPhone”，不返回 “iphone”）
- 词频数据必须接入——哪怕只是本地统计的
word_freq_map，把距离为 1 的 “their” 和 “there” 按频率加权排序 - 对键盘邻近错误建模：q-w-e-r 一行内替换代价设为 0.5，跨行替换设为 1.0（需预定义
keyboard_layout映射表） - 避免返回语法明显错误的词，比如输入动词原形却返回名词（需轻量词性标注或后缀规则，如 “-ing” “-ed” 优先匹配动词变体）
C++ 标准库没有现成编辑距离函数，别依赖 std::string 成员
std::string 的 find、replace 等完全不解决编辑距离问题。网上搜到的所谓 “C++ 编辑距离函数” 很多是误传或封装了第三方库（如 Boost.StringAlgorithms），但 Boost 并未提供标准编辑距离实现。
务必自己实现，且注意细节：
- 使用
size_t要小心：DP 表索引必须用有符号 int，否则i-1下溢成极大正数 - 输入字符串建议转
std::u8string或确保 ASCII-only；UTF-8 多字节字符需先解码为 Unicode code point 再处理，否则一个 ‘é’ 算 2 个编辑操作 - 不要用
std::string::operator[]直接取 char——它取的是字节，不是字符；对英文单词可接受，但代码里得写清楚注释限定适用范围
最简可用版本就是双层 for 循环 + 二维 vector，别绕弯子引入外部依赖。纠错逻辑越靠近业务层，越容易根据产品需求调整权重和规则。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
