Levenshtein距离需用动态规划避免指数级递归，标准二维DP时间复杂度O(mn)不可降，但空间可优化至O(min(m,n))：先交换使短串为列，再用两行滚动数组或一维数组+双变量更新，并严格初始化边界与索引偏移。
Levenshtein 距离怎么算才不超时？
直接递归实现 levenshtein 会指数级爆炸，实际项目里必须用动态规划二维数组。空间可以优化到 O(min(m, n))，但初学者先用 O(m * n) 更安全——尤其当词典单词平均长度
常见错误是边界初始化写错：第 0 行应为 0,1,2,...,n（插入），第 0 列为 0,1,2,...,m（删除）。别漏掉 dp[i][j] = dp[i-1][j-1] 这个“字符相等”分支。
int levenshtein(const string& a, const string& b) {
int m = a.size(), n = b.size();
vector<vector<int>> dp(m+1, vector<int>(n+1));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) {
if (a[i-1] == b[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
}
return dp[m][n];
}
查词典时要不要全遍历？
如果词典有 10 万单词，每次纠错都调用 levenshtein 算一遍，最坏 O(N * m * n)，交互延迟明显。实际中得加剪枝：
- 先按长度粗筛：只查
abs(len - query_len) <= max_dist的候选词 - 计算中提前终止：比如设
max_dist = 2，某轮内dp[i][j] > max_dist就直接return max_dist + 1 - 避免重复计算：对同一
query缓存结果，用unordered_map<string, vector<string>>存最近 100 个
别一上来就上 BK-tree 或 Trie —— 那些适合百万级词典或高频服务，小项目纯属过度设计。
立即学习“C++免费学习笔记（深入）”；
为什么“cat”→“cut”距离是 1，但“abc”→“acb”却是 2？
Levenshtein 只允许插入、删除、替换三种操作，不支持相邻字符交换（那是 Damerau-Levenshtein）。所以 "abc" → "acb" 必须先删 'b'（位置 1），再在位置 1 插入 'b'，共两步；不能“交换”一步到位。
如果你的场景常需处理拼写颠倒（比如打字手滑），要么改用 Damerau 版本（多一个判断 i > 1 && j > 1 && a[i-1]==b[j-2] && a[i-2]==b[j-1]），要么在纠错后额外检查交换邻位是否更优。
注意：标准 std::string 没内置距离函数，别误以为 string::compare 能干这事——它只是字典序比较。
如何让纠错结果按相关性排序？
单纯按 Levenshtein 距离升序不够：距离同为 1 的 "the" 和 "tea"，用户更可能想输 "the"（高频词）。所以得加权重：
- 用词频做乘数：
score = distance + (1.0 / (freq + 1))，频次越高得分越低 - 首字母匹配加分：若
query[0] == candidate[0]，给-0.3奖励 - 长度差惩罚：避免把
"and"错纠成"android"，加abs(len_diff) * 0.5
别硬编码所有规则——先跑个真实日志样本，看前 10 个 bad case 是什么模式，再针对性调权。很多“智能”其实是靠人工观察补出来的。
真正难的不是算距离，而是定义什么叫“更好”的纠正：用户打错时的心理路径（漏字母？多按？键盘邻键？）比算法本身更影响效果。
