字符串编辑距离算法详解 - 最少编辑次数计算

字符串编辑距离是指两个字符串间的最小编辑次数，通常用于比较字符串的相似度。

编辑可以包括插入、删除和替换操作，每个操作的代价可以不同。例如，我们可以定义插入和删除操作的代价为1，替换操作的代价为2，则字符串'abc'和'abde'的编辑距离为3，因为我们需要将'abc'替换为'abd'，再插入一个'e'。

求两个字符串的最小编辑距离是一个经典的动态规划问题。我们设dp[i][j]为将字符串1的前i个字符转换为字符串2的前j个字符所需的最小编辑距离。则有以下状态转移方程：

• 当s1[i] == s2[j]时，dp[i][j] = dp[i-1][j-1]；
• 当s1[i] != s2[j]时，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + cost；其中cost为将s1[i]替换为s2[j]的代价。

最终的答案为dp[m][n]，其中m和n分别为两个字符串的长度。

时间复杂度为O(mn)，空间复杂度也为O(mn)，可以通过空间压缩将空间复杂度优化为O(n)。