编辑距离函数需将dp数组行列各扩1，第0行/列初始化为0到s2.length()和0到s1.length()，递推时i、j从1开始，访问s1[i-1]和s2[j-1]；避免递归因栈溢出和哈希开销。
编辑距离函数怎么写才不越界
直接用二维数组实现 edit_distance 时，最常崩在访问 dp[i-1][j-1] 或 dp[i][j-1] 越界——尤其当字符串为空或长度为 1。别硬套公式，先扩一格：让 dp 行数 = s1.length() + 1，列数 = s2.length() + 1，第 0 行/列对应空串到目标串的插入/删除代价。
常见错误现象：std::out_of_range 或静默脏数据；更隐蔽的是把循环从 i = 0 开始，却没初始化第 0 行/列。
- 初始化：第 0 行填
0, 1, 2, ..., s2.length()（空串变s2全靠插入）；第 0 列同理 - 递推时
i和j从 1 开始，对应比较s1[i-1]和s2[j-1]，避免下标错位 - 如果用
vector<vector>></vector>，别忘了预分配尺寸，否则push_back带来额外开销且易出错
为什么不用递归+记忆化而选迭代DP
纯递归写 edit_distance 看似简洁，但 C++ 没尾递归优化，深度稍大（比如长度 > 50）就栈溢出；加 map<pair>, int></pair> 记忆化又引入哈希开销和指针间接访问，实测比二维数组慢 3–5 倍。
使用场景：在线服务做模糊匹配、拼写纠错、Git diff 启发式预处理——这些都要求毫秒级响应，且输入长度可控（通常
立即学习“C++免费学习笔记（深入）”；
- 迭代 DP 时间复杂度稳定
O(m*n)，空间可优化到O(min(m,n))（滚动数组），但初学建议先写清二维版 - 若真要省空间，只保留两行：
prev_row和curr_row，注意更新顺序和临时变量存diag值 - 别为了“省空间”提前用
short存距离——编辑距离可能超 32767，int更安全
Levenshtein 距离和实际字符串相似度不是一回事
edit_distance 返回的是最小操作数，不是 [0,1] 区间内的相似度。直接拿它当相似度用会出问题：两个长串编辑距离是 5，看着小，但相对长度可能只有 1% 差异；两个短串距离是 2，却可能已面目全非。
参数差异：有人除以 max(len1, len2)，有人除以 len1 + len2，还有人用 1 - distance / (double)max(...)。没有标准答案，取决于业务。
- 搜索场景常用
1.0 - distance / (double)max(s1.size(), s2.size())，对长度敏感 - 去重场景倾向
distance ，避免长串误判 - 别在循环里反复调用
s1.size()和s2.size()，C++11 后它们是 O(1)，但存成const size_t n = s1.size()更清晰
字符粒度陷阱：UTF-8 字符串不能直接用 string[i]
用 std::string 存中文、emoji 时，s1[i] 取到的是 UTF-8 字节而非字符，导致 edit_distance 在字节层面算错——比如一个汉字占 3 字节，会被当成 3 个“字符”处理，距离暴涨。
使用场景：用户昵称、地址、日志关键词匹配等含多语言文本的系统。
- 真正要比较的是 Unicode 码点，得先用 ICU、utf8cpp 或手写解码把
std::string转成std::vector<char32_t></char32_t>再跑 DP - 如果只是英文+数字为主，且明确约定输入为 ASCII，那直接用
string没问题，但必须在接口注释里写死 “ASCII-only” - 别用
std::wstring试图绕过——Windows 下是 UTF-16，Linux 下常是 UCS-4，跨平台反而更乱
最麻烦的不是算法本身，而是你得先确认输入到底是不是你想的“字符”。没做编码清洗就上编辑距离，结果再准也没意义。
