编辑距离函数应分配(m+1)×(n+1)数组，dpi表示s1前i字符到s2前j字符的距离，初始化dpi=i、dp0=j，循环中用s1[i-1]==s2[j-1]比较，避免下标越界。
编辑距离函数怎么写才不踩内存越界坑
直接用动态规划实现 edit_distance 时，常见错误是二维数组下标从 1 开始但初始化没对齐，导致访问 dp[-1][j] 或越界读写。正确做法是分配 (m+1) × (n+1) 的数组，让 dp[i][j] 表示 s1.substr(0,i) 到 s2.substr(0,j) 的距离。
关键细节：
- 初始化
dp[i][0] = i、dp[0][j] = j（空串变长度为 i/j 的串需 i/j 次操作） - 循环从
i=1到m、j=1到n，避免负下标 - 字符比较用
s1[i-1] == s2[j-1]，不是s1[i] == s2[j] - 若只关心是否 ≤ 某阈值（如 2），可在内层循环中加 early break：一旦整行最小值 > 阈值且无法回退，可提前返回
如何快速匹配词典里最接近的单词
对每个查询词，暴力遍历整个词典算一遍 edit_distance 效率极低——10 万词典 × 每次 O(mn) 足够卡住交互响应。必须优化搜索路径。
实用策略：
立即学习“C++免费学习笔记（深入）”；
- 预筛选：先按长度过滤，只保留
abs(len(query) - len(candidate)) ≤ max_edit的候选词（编辑距离不可能小于长度差） - 剪枝计算：在 DP 过程中，一旦当前行累计操作数 >
max_edit，立即终止该候选词计算（可用一维滚动数组 + 提前退出） - 不依赖第三方库时，避免用
std::string频繁 substr，改用const char*+ 长度参数传入距离函数，减少拷贝 - 若词典稳定，可离线构建 BK-tree（基于编辑距离的度量树），查询复杂度降到平均 O(log n)，但插入/更新代价高，适合只读场景
大小写、非字母字符怎么处理才不影响纠错逻辑
原始编辑距离对大小写敏感，"Apple" 和 "apple" 会算出距离 1，但这不是拼写错误，是格式问题。纠错前必须归一化。
推荐做法：
- 统一转小写再计算（用
std::tolower遍历，别用std::transform+std::toupper混用 locale，容易在非 ASCII 字符上出错） - 跳过标点和空格：不是删除它们，而是将 query 和 candidate 同时提取「纯字母序列」后再比（例如
"can't"→"cant"，否则撇号会干扰距离判断） - 数字保留原样，但可加规则：若 query 含数字而词典项全为字母，直接排除（除非业务明确要支持“v2ray”类混排词）
- 注意：归一化后的字符串仅用于距离计算，最终返回的纠错结果仍应是词典中原格式词（如词典存的是
"iPhone"，不能返回"iphone"）
为什么 Levenshtein 距离不够用，还得加权重和常见错误模型
纯编辑距离会把 "hte" → "the"（换位）和 "hte" → "she"（替换）都判为距离 2，但前者更可能是真实拼写错误。需要补充语言学先验。
轻量增强方式：
- 给「相邻字母交换」（transpose）操作赋权重 1（而非标准 Lev 的 2），即实现 Damerau-Levenshtein 距离
- 对键盘邻近键替换加权：如
'q'和'w'、'a'和's'算成本 0.5，其他替换算 1.0（需预定义邻近映射表） - 高频拼错对单独建表：如
"recieve" → "receive"、"seperate" → "separate"，匹配到直接返回，不走距离计算 - 注意：加权后不能再用整数 DP 表，得用
float或定点小数，且阈值判断要相应调整（比如最大允许加权距离设为 1.8 而非 2）
真正难的不是算法本身，是边界情况的取舍：用户输错一个长单词的中间部分，该优先返回同前缀的词，还是编辑距离更小但前缀不同的词？这得靠业务语料调优，没有通用解。
