如何实现字符串编辑距离算法？

字符串编辑距离问题是计算两个字符串之间的编辑距离,允许的编辑操作有:插入一个字符、移除一个字符、替换一个字符。我们可以使用动态规划实现字符串编辑距离算法:

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) 
                dp[i][j] = dp[i - 1][j - 1];
            else 
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1; 
        }
    }

    return dp[m][n];
}

算法流程:

1. 初始化dp数组,dp[i][j]表示word1的前i个字符与word2的前j个字符的编辑距离。
2. 当i=0或j=0时,dp[i][0]=i和dp[0][j]=j,表示一个字符串为空时,编辑距离为另一个字符串的长度。
3. 当两个字符相等时,dp[i][j] = dp[i-1][j-1]。因为最后一个字符不需要编辑。
4. 当两个字符不等时,dp[i][j]为三个值的最小值加1:
   • dp[i-1][j-1]:替换操作,替换最后一个字符。
   • dp[i][j-1]:插入操作,在word1插入与word2最后一个字符相同的字符。
   • dp[i-1][j]:移除操作,从word1移除最后一个字符。
5. 重复步骤3和4,最终dp[m][n]为编辑距离,返回该值。

时间复杂度O(mn),空间复杂度O(mn)。

所以,字符串编辑距离的关键是:

1. 定义dp数组,dp[i][j]表示两个字符串前i和前j个字符的编辑距离。
2. 处理边界,当一个字符串为空时,编辑距离为另一个字符串的长度。
3. 若两个字符相等,编辑距离不增加。
4. 若两个字符不等,编辑距离为三个操作的最小值加1:替换、插入和移除。
5. 重复以上步骤,dp[m][n]为最终编辑距离。