levenshtein编辑距离的三种优化：一、滚动数组将空间降至o(min(m,n))；二、边界剪枝通过阈值提前终止；三、只读内存优化减少拷贝与类型转换开销。
如果您需要计算两个字符串之间的编辑距离，Levenshtein算法提供了一种基于动态规划的经典解法。该算法通过构建二维状态表记录插入、删除、替换三种操作的最小代价，但标准实现存在空间冗余。以下是几种降低空间复杂度并提升局部缓存效率的优化思路及对应源码实现：
一、滚动数组优化：将空间复杂度从O(m×n)降至O(min(m,n))
标准Levenshtein算法使用m×n二维数组存储所有子问题结果，但每次递推仅依赖上一行与当前行，因此可仅保留两行数据进行迭代更新。当字符串长度差异较大时，应以较短字符串长度作为滚动维度以节省内存。
1、确定s1与s2中长度较小者，记为short_str，较长者为long_str；
2、声明两个一维vector
3、初始化prev_row[i] = i（表示空字符串到short_str前i个字符的编辑距离）；
4、遍历long_str的每个字符，对每个j∈[1, short_str.length()]，按公式计算curr_row[j]：curr_row[j] = min({prev_row[j] + 1, curr_row[j-1] + 1, prev_row[j-1] + (long_str[i-1] != short_str[j-1])})；
5、每轮结束后交换prev_row与curr_row指针，进入下一轮迭代。
二、边界剪枝优化：提前终止无必要计算的子路径
当两字符串长度差超过预设阈值（如最大允许编辑距离d），可立即返回大于d的结果，避免完整DP表填充。该策略在模糊匹配场景中显著减少无效计算，尤其适用于仅需判断是否“足够相似”的情形。
1、设max_dist为用户指定的最大可接受编辑距离；
2、若abs((int)s1.length() - (int)s2.length()) > max_dist，直接返回max_dist + 1；
3、初始化DP数组时仅分配宽度为2 * max_dist + 1的带状区域，中心对齐字符索引；
4、对s1中每个位置i，仅更新s2中满足|i - j| ≤ max_dist的j范围内的状态；
5、若某轮中所有候选j对应的状态值均大于max_dist，则立即返回max_dist + 1。
三、只读内存优化：利用const引用与无符号整型减少拷贝与符号扩展开销
原始实现常以std::string传值或重复调用length()引发隐式拷贝与函数调用开销。通过const std::string&传参、预存长度为size_t类型，并使用unsigned char比较字符，可提升内层循环执行效率。
1、函数签名定义为int levenshtein(const std::string& s1, const std::string& s2, int max_dist = -1)；
2、在函数开头声明const size_t len1 = s1.length(), len2 = s2.length()；
3、在状态转移中，将字符比较写作static_cast
4、所有循环变量i、j均声明为size_t类型，避免有符号/无符号混合比较警告；
5、当max_dist ≥ 0且当前计算出的最小可能剩余距离（如abs((int)(len1-i) - (int)(len2-j))）与已有最优值之和已超max_dist时，跳过该状态更新。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
