编辑距离需通过提前剪枝、滚动数组和长度过滤优化，避免O(m×n)超时：先按长度分桶，再对桶内词用带early-return的DP计算，且仅当|len_a−len_b|≤max_dist时才执行。
编辑距离怎么算才不超时
标准动态规划求两个字符串的编辑距离，时间复杂度是 O(m×n)，对长词或大批量候选词（比如词典有 10 万单词）直接套用会明显卡顿。实际纠错中，目标词长度固定（比如用户输错的 "recieve"），但候选词数量大，不能对每个都跑一遍完整 DP。
关键优化点：提前剪枝 + 限制最大允许编辑距离（通常设为 1 或 2）。用「带边界的 DP 表」或更轻量的「递归 + 记忆化 + 剪枝」更实用：
- 初始化时只开
dp[3][n+1]（滚动数组），因为只关心编辑距离 ≤2 的情况 - 递归中一旦当前操作数 > 最大容忍值（如 2），立刻返回
INT_MAX - 加一个「长度差绝对值 > 最大容忍值」的快速过滤，比如
abs(len_a - len_b) > 2直接跳过
如何从字典里快速找编辑距离 ≤2 的候选词
暴力遍历整个词典在 C++ 中可行但不优雅；真正线上场景必须提速。不建议手写哈希或前缀树来加速编辑距离搜索——那反而增加复杂度。
更务实的做法是预处理 + 分层筛选：
立即学习“C++免费学习笔记（深入）”；
- 先按长度分桶：
map<size_t vector>></size_t>，查"recieve"（长度 8）时只查长度为 6/7/8/9/10 的桶 - 对每个桶内单词，用优化版
edit_distance(a, b, max_dist=2)判断，函数内部带 early-return - 如果词典稳定，可预先计算所有词对「首字母 + 长度」的组合索引，进一步缩小范围
注意：不要用 std::string::compare 或 == 替代编辑距离判断——它们只判相等，无法捕获 "teh" → "the" 这类单字符换位。
levenshtein_distance 的 C++ 实现要注意什么
网上很多版本漏掉「替换成本为 0 当字符相等」这个逻辑，导致 "abc" 和 "abc" 算出距离为 3。正确实现必须在状态转移时判断 a[i-1] == b[j-1]。
一个轻量、可内联的版本示例：
int levenshtein_distance(const string& a, const string& b, int max_cost = 2) {
size_t m = a.size(), n = b.size();
if (abs((long)m - (long)n) > max_cost) return max_cost + 1;
vector<vector<int>> dp(2, vector<int>(n + 1));
for (int j = 0; j <= n; ++j) dp[0][j] = j;
for (size_t i = 1; i <= m; ++i) {
dp[i%2][0] = i;
for (size_t j = 1; j <= n; ++j) {
int cost = (a[i-1] == b[j-1]) ? 0 : 1;
dp[i%2][j] = min({dp[(i-1)%2][j] + 1,
dp[i%2][j-1] + 1,
dp[(i-1)%2][j-1] + cost});
if (dp[i%2][j] > max_cost) dp[i%2][j] = max_cost + 1;
}
if (dp[i%2][n] > max_cost) return max_cost + 1;
}
return dp[m%2][n];
}重点：第三行提前退出、滚动数组节省空间、每行末尾检查是否已超限。
为什么拼写纠错不能只靠编辑距离
编辑距离会把 "dogg" 同等地匹配到 "dog" 和 "fog"（距离都是 1），但直觉上前者更可能——因为多打了一个重复字符，属于常见输入错误；而后者是完全不同的音节。
真实系统里，编辑距离只是第一道筛子。后续必须叠加：
- 键盘邻近度（
'd'和'f'在 QWERTY 上相邻，'d'和'g'不邻近） - 常见错误模式库（如
"ie"/"ei"错序、双写字母误删） - 词频加权（词典中
"dog"出现频次远高于"fog"，应优先返回）
纯靠 levenshtein_distance 返回多个等距结果时，不排序、不加权，用户看到的纠错建议就不可靠。这点容易被忽略，但恰恰决定体验上限。
