Levenshtein算法用动态规划计算两字符串最小编辑距离，通过(m+1)×(n+1)二维DP表，初始化边界后按字符匹配与否更新状态，最终结果为dpm，可优化至O(min(m,n))空间。
如果您需要在 C++ 中计算两个字符串之间的编辑距离，Levenshtein 算法是一种经典且精确的动态规划解法。该算法通过构建二维状态表，记录将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除、替换）。以下是实现该算法的具体步骤：
一、定义状态与初始化二维 DP 表
Levenshtein 算法使用 dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑距离。状态表维度为 (m+1) × (n+1)，其中 m 和 n 分别为两字符串长度。首行和首列表示空字符串到目标子串的编辑距离，需按索引值初始化。
1、声明两个字符串变量 str1 和 str2，分别存储输入的源字符串和目标字符串。
2、获取 str1.length() 赋值给 m，str2.length() 赋值给 n。
3、创建二维 vector
4、使用循环将 dp[i][0] 初始化为 i（i 从 0 到 m），表示 str1 前 i 个字符变为空串需 i 次删除。
5、使用循环将 dp[0][j] 初始化为 j（j 从 0 到 n），表示空串变为 str2 前 j 个字符需 j 次插入。
二、填充 DP 表并处理字符匹配
状态转移依据当前字符是否相等：若 str1[i-1] == str2[j-1]，则无需编辑，直接继承左上角值；否则取左、上、左上三方向最小值加 1，对应替换、删除、插入三种操作。
1、使用双重 for 循环，i 从 1 到 m，j 从 1 到 n。
2、在内层循环中判断 if (str1[i-1] == str2[j-1])，成立时执行 dp[i][j] = dp[i-1][j-1]。
3、否则执行 dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1。
4、确保每次赋值后 dp[i][j] 始终保持为整型最小编辑距离值。
三、返回结果并优化空间复杂度（可选）
标准实现以二维表完成全部状态更新，最终结果位于 dp[m][n]。若仅需返回距离值而无需回溯操作路径，可将空间复杂度从 O(m×n) 优化至 O(min(m,n))，使用滚动数组只保留两行状态。
1、在函数末尾直接 return dp[m][n];
2、若采用空间优化方案，声明两个一维 vector
3、初始化 prev[j] = j（j 从 0 到 n）。
4、外层循环 i 从 1 到 m，内层 j 从 1 到 n，按相同转移逻辑更新 curr[j]。
5、每次内层循环结束后执行 prev = curr;，继续下一轮迭代。
四、封装为可调用函数并处理边界情况
为增强鲁棒性，函数应检查空字符串输入，并支持 const 引用传参避免拷贝开销。同时确保所有变量作用域清晰，无未定义行为。
1、定义函数签名 int levenshteinDistance(const string& str1, const string& str2);
2、在函数开头添加 if (str1.empty()) return static_cast
3、添加 if (str2.empty()) return static_cast
4、声明 m 和 n 为 size_t 类型，但在后续计算中显式转换为 int 用于 vector 下标和返回值。
5、确保所有 vector 索引访问均在合法范围内，禁止使用负数或越界下标。
五、完整可编译代码片段（含主函数示例）
以下为可直接编译运行的最小完整示例，包含头文件引入、命名空间声明及测试用例输出。
1、包含必要头文件：#include
2、在 main 函数中定义测试字符串 string a = "kitten"; string b = "sitting";
3、调用 levenshteinDistance(a, b)，并将结果输出至 std::cout。
4、验证输出是否为 3，对应 k→s、e→i、末尾插入 g 三次操作。
5、添加另一组测试：string c = ""; string d = "abc"; 输出应为 3。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
