编辑距离问题与动态规划

编辑距离问题与动态规划

编辑距离（Edit Distance），又称Levenshtein距离，是指通过插入、删除、替换字符的方式将一个字符串转换为另一个字符串所需的最小操作数。这个问题在自然语言处理、拼写检查、DNA序列比对等领域中都有广泛的应用。在本文中，我们将介绍编辑距离的概念，并使用动态规划来解决这个问题。

问题描述

给定两个单词 word1 和 word2，我们的任务是找到将 word1 转换为 word2 所需的最小操作数。可以进行以下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

下面我们将通过示例来说明如何计算编辑距离。

示例 1

输入:

word1 = "horse", word2 = "ros"
1

输出:

3
1

解释:

1. “horse” -> “rorse” (将 ‘h’ 替换为 ‘r’)
2. “rorse” -> “rose” (删除 ‘r’)
3. “rose” -> “ros” (删除 ‘e’)

示例 2

输入:

word1 = "intention", word2 = "execution"
1

输出:

5
1

解释:

1. “intention” -> “inention” (删除 ‘t’)
2. “inention” -> “enention” (将 ‘i’ 替换为 ‘e’)
3. “enention” -> “exention” (将 ‘n’ 替换为 ‘x’)
4. “exention” -> “exection” (将 ‘n’ 替换为 ‘c’)
5. “exection” -> “execution” (插入 ‘u’)

动态规划解决编辑距离问题

为了解决编辑距离问题，我们可以使用动态规划。我们将创建一个二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数。

动态规划的状态转移方程如下：

dp[i][j] = dp[i-1][j-1]  # 如果 word1[i] == word2[j]，无需操作
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1  # 否则，取插入、删除、替换三种操作的最小值
1
2

我们需要初始化 dp 数组的第一行和第一列，以处理边界情况。

下面是 Java 代码实现：

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int 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], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
            }
        }
        
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

示例

使用上述的 Solution 类，我们可以解决示例中提到的问题。

public static void main(String[] args) {
    Solution solution = new Solution();
    String word1 = "horse";
    String word2 = "ros";
    int distance = solution.minDistance(word1, word2);
    System.out.println("编辑距离: " + distance);  // 输出 3
}
1
2
3
4
5
6
7

public static void main(String[] args) {
    Solution solution = new Solution();
    String word1 = "intention";
    String word2 = "execution";
    int distance = solution.minDistance(word1, word2);
    System.out.println("编辑距离: " + distance);  // 输出 5
}
1
2
3
4
5
6
7

这段代码演示了如何使用 Solution 类来计算两个单词之间的编辑距离。

编辑距离问题是一个经典的动态规划问题，它可以用于多种应用中，包括拼写检查、自然语言处理、文本相似度计算等。通过动态规划，我们可以高效地找到最小编辑距离，以解决这些问题。