Levenshtein距离必须用动态规划，因纯递归时间复杂度O(3^n)且易栈溢出；二维DP表初始化第0行/列为j/i，转移时字符相等则继承左上角，否则取min(删、插、替)+1，空间可优化至O(min(m,n))。
Levenshtein距离计算必须用动态规划，递归会爆栈
直接写递归版 levenshtein_distance 在稍长字符串（比如 >20 字符）上极易栈溢出，且重复子问题多、时间爆炸。必须用二维 DP 表，空间可优化到 O(min(m,n))，但初版先保正确性。
常见错误是边界初始化错：第 0 行/列应为 i 和 j（插入/删除代价），不是全 0；状态转移漏掉替换操作的 +1。
- 输入字符串建议统一转小写再比，避免大小写干扰语义
- 若词典量大（>10k 单词），别对每个候选词都算完整 DP——先快速过滤长度差 > 阈值的项
-
std::string的.data()或.c_str()可传给 C 风格函数，但注意空终止符；C++20 起推荐用std::span管理字符视图
构建候选词集时，别只查 Levenshtein=1 的单词
用户输错 “recieve”，真实拼写是 “receive” —— Levenshtein 距离为 2（i/e 互换 + e/i 互换），但若只返回距离 ≤1 的结果，就漏掉了正确答案。实际场景中，距离为 2 的候选更常见。
典型误判是硬设阈值为 1：键盘邻位错（如 “qwe” → “qew”）、双字母漏输（“address” → “adres”）、元音替换（“definately” → “definitely”）基本都落在距离 1–2 区间。
立即学习“C++免费学习笔记（深入）”；
- 建议阈值设为
std::min(2, std::max(s.length(), dict_word.length()) / 3)，兼顾短词敏感性和长词容错 - 预处理词典时，可按长度分桶，查词前先定位到 ±2 长度范围内的桶，跳过大量无关项
- 避免对整个词典暴力扫：用
std::unordered_set存原始词，再用std::vector存按长度分组的副本
std::string_view 能省掉多次构造，但要注意生命周期
在纠错主循环里反复传 std::string 值参，会触发多次堆分配和拷贝。改用 std::string_view 是标准解法，但容易踩坑：它不拥有数据，若传入的原始字符串临时对象已析构，string_view 就悬空。
典型错误是这样写：auto sv = std::string_view(input.c_str()); —— c_str() 返回指针依赖 input 生命周期，而 input 若是函数参数且为右值，可能已在下一行销毁。
- 安全做法：输入参数用
const std::string&或std::string_view，并确保调用方维持源字符串存活 - 词典加载后存为
std::vector<:string></:string>，再建std::vector<:string_view></:string_view>映射，避免string_view指向局部变量 - VS2019+ 和 GCC9+ 对
string_view的substr()优化较好，但 Clang12 前需留意其内部实现是否复制
性能瓶颈往往卡在内存分配，不是算法本身
实测中，90% 时间花在 std::vector 动态扩容、std::string 构造/析构，而非 DP 循环。一个 5 万词的词典，每词平均比对 10 次，光 string 构造就能吃掉 200ms+。
最容易被忽略的是临时容器：比如每次纠错都 new 一个 std::vector<:pair std::string>></:pair> 存候选，不如复用一个成员变量 vector 并调用 .clear()。
- DP 表用
std::vector<int></int>而非std::vector<:vector>></:vector>，手动做一维滚动数组（prev_row,curr_row） - 候选结果排序前，先用
std::partial_sort取 top-K，别全排序；K 通常取 3–5 足够 - 若嵌入服务长期运行，考虑用
std::pmr::vector+ 自定义内存池，避免频繁 malloc/free
真正难的不是算出距离，是怎么让 10 万词典在 10ms 内返回前三推荐——得从内存视角重新组织整个流程。
