编辑距离计算需正确初始化dpi=i、dp0=j，转移时用s1[i-1]==s2[j-1]避免越界；查≤2候选词应预建变形哈希表+分层搜索；词典宜分桶+string_view优化；纠错宜用带剪枝的trie而非unordered_set。
编辑距离计算函数怎么写才不出错
编辑距离（Levenshtein Distance）是单词纠错的核心，但手写时容易在边界处理和循环方向上出错。常见错误是把 dp[i][j] 定义成“前 i 个字符到前 j 个字符”，却在初始化或转移时漏掉空字符串情况，导致 "a" 和 "" 距离算成 0 而非 1。
- 务必初始化
dp[i][0] = i、dp[0][j] = j，对应插入/删除全操作 - 状态转移只依赖左、上、左上三个格子，用二维数组即可，不需要滚动数组——纠错场景下词典规模通常不大，可读性比省那点内存重要
- 注意字符比较用
s1[i-1] == s2[j-1]，下标别越界；C++ 中string索引从 0 开始，而dp表行列对应长度，这是最常踩的坑
如何快速查出编辑距离 ≤2 的候选词
暴力遍历整个词典对每个输入词都算一遍编辑距离，O(N×M²) 复杂度在词典超 10 万词时明显卡顿。不能只靠优化单次距离计算，得从检索结构入手。
- 预建
std::unordered_map<:string std::vector>></:string>，键为所有可能的“变形键”：对每个词生成所有编辑距离为 1 的变体（删/增/换/邻位交换），值存原词——这样查"helo"时，只需生成它的所有距离 1 变体（如"hello"、"heo"、"helo"自身等），再查哈希表 - 距离为 2 的候选，不要双重嵌套生成所有距离 2 变体（爆炸式增长），而是对距离 1 的每个候选，再跑一次距离 ≤1 的搜索——实际中 95% 的拼错都在距离 1 内，距离 2 仅需兜底
- 避免重复：用
std::set<:string></:string>收集结果，最后转 vector 并按距离、词频排序
为什么直接用 std::string 做词典加载会慢
词典文本文件逐行读入 std::string 向量看似简单，但纠错时频繁字符串拷贝和内存分配会拖慢响应。尤其当词典含 50 万词，每次纠错都要遍历或哈希查找，构造成本不可忽视。
- 用
std::vector<:string_view></:string_view>替代std::vector<:string></:string>存储词典——前提是词典字符串生命周期长于纠错模块（例如全局 const char* 数组或 mmap 映射的只读内存） - 词典加载时，把所有词按长度分桶：
std::unordered_map<size_t std::vector>></size_t>，查询前先根据输入长度 ±2 过滤桶，跳过明显不可能匹配的长词或短词 - 避免在纠错热路径中调用
std::string::substr()或operator+，它们隐式分配；改用std::string_view切片 + 原始指针比较
std::unordered_set 里存词典还是用 trie 更合适
单纯查“是否存在”用 std::unordered_set 没问题，但纠错需要找近似词，这时候哈希表就帮不上忙了——它不支持前缀匹配或编辑距离邻域搜索。trie 是更自然的选择，尤其配合 Damerau-Levenshtein（支持邻位交换）剪枝。
立即学习“C++免费学习笔记（深入）”；
- 标准 trie 不直接支持编辑距离，但可在 DFS 过程中维护当前编辑距离，一旦超过阈值（如 2）就剪枝；递归栈深度最多为输入长度 + 阈值，可控
- 用
std::array<:shared_ptr>, 26></:shared_ptr>实现子节点，比std::map<char node></char>快且内存连续；假设词典全小写 ASCII，不用泛化到 Unicode - 如果词典固定不变，考虑用双数组 trie（DAT）压缩内存——但实现复杂，小项目优先用朴素 trie + 剪枝，实测 10 万词下平均响应在 0.5ms 内
编辑距离本身不难，真正影响效果的是词频加权和上下文——比如 "form" 和 "from" 距离为 1，但用户打 "form" 时大概率想输 "from"，这需要额外统计语料中词对共现概率。纯编辑距离只是起点，不是终点。
