题目: 编辑距离

来自智得网
跳转至： 导航、​ 搜索

方法一：动态规划

这是一个经典的动态规划问题，可以使用一个二维数组 dp 来表示状态，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。如果 word1[i-1] == word2[j-1]，那么 dp[i][j] 就等于 dp[i-1][j-1]，因为此时不需要进行任何操作。否则，可以进行插入、删除或替换操作，dp[i][j] 可以通过以下三种方式转移而来：

  • 插入操作：dp[i][j] = dp[i][j-1] + 1，即将 word2[j-1] 插入到 word1 的前 i 个字符中。
  • 删除操作：dp[i][j] = dp[i-1][j] + 1，即将 word1[i-1] 删除。
  • 替换操作：dp[i][j] = dp[i-1][j-1] + 1，即将 word1[i-1] 替换为 word2[j-1]。

具体的状态转移方程如下：

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

初始条件为 dp[i][0] = i 和 dp[0][j] = j，表示一个字符串为空时转换到另一个字符串需要的操作次数。

最终的答案就是 dp[m][n]，其中 m 和 n 分别是 word1 和 word2 的长度。 

int minDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    
    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[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
            }
        }
    }
    
    return dp[m][n];
}

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];
}

func minDistance(word1 string, word2 string) int {
    m := len(word1)
    n := len(word2)
    
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
            }
        }
    }
    
    return dp[m][n]
}

func min(a, b, c int) int {
    if a < b && a < c {
        return a
    } else if b < c {
        return b
    } else {
        return c
    }
}

def minDistance(word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)
    
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    for i in range(m+1):
        dp[i][0] = i
    
    for j in range(n+1):
        dp[0][j] = j
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    
    return dp[m][n]

方法二：递归

除了动态规划，我们还可以使用递归的方法来求解编辑距离问题。具体步骤如下：

  1. 定义一个递归函数，传入两个字符串 word1 和 word2，以及它们的索引 i 和 j。
  2. 若 i 等于字符串 word1 的长度，返回 word2 的长度减去 j。
  3. 若 j 等于字符串 word2 的长度，返回 word1 的长度减去 i。
  4. 若 word1[i] 等于 word2[j]，递归调用函数，传入 i+1 和 j+1，并返回结果。
  5. 若 word1[i] 不等于 word2[j]，递归调用函数，分别传入 i+1 和 j，i 和 j+1，并返回三者的最小值加一。
int minDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    
    vector<int> dp(n+1, 0);
    
    for (int j = 1; j <= n; j++) {
        dp[j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        int prev = dp[0];
        dp[0] = i;
        
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (word1[i-1] == word2[j-1]) {
                dp[j] = prev;
            } else {
                dp[j] = min(prev, min(dp[j], dp[j-1])) + 1;
            }
            prev = temp;
        }
    }
    
    return dp[n];
}

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    
    int[] dp = new int[n+1];
    
    for (int j = 1; j <= n; j++) {
        dp[j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        int prev = dp[0];
        dp[0] = i;
        
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[j] = prev;
            } else {
                dp[j] = Math.min(prev, Math.min(dp[j], dp[j-1])) + 1;
            }
            prev = temp;
        }
    }
    
    return dp[n];
}

func minDistance(word1 string, word2 string) int {
    m := len(word1)
    n := len(word2)
    
    dp := make([]int, n+1)
    
    for j := 1; j <= n; j++ {
        dp[j] = j
    }
    
    for i := 1; i <= m; i++ {
        prev := dp[0]
        dp[0] = i
        
        for j := 1; j <= n; j++ {
            temp := dp[j]
            if word1[i-1] == word2[j-1] {
                dp[j] = prev
            } else {
                dp[j] = min(prev, min(dp[j], dp[j-1])) + 1
            }
            prev = temp
        }
    }
    
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def minDistance(word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)
    
    dp = [0] * (n+1)
    
    for j in range(1, n+1):
        dp[j] = j
    
    for i in range(1, m+1):
        prev = dp[0]
        dp[0] = i
        
        for j in range(1, n+1):
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                dp[j] = prev
            else:
                dp[j] = min(prev, min(dp[j], dp[j-1])) + 1
            prev = temp
    
    return dp[n]

方法三：优化空间复杂度的动态规划

在动态规划的方法中，我们使用一个二维数组来存储状态转移的结果。但是可以观察到，在计算 dp[i][j] 的过程中，我们只需要用到上一行和当前行的结果。因此，我们可以只使用两个一维数组来存储状态，从而优化空间复杂度。

具体步骤如下：

  1. 定义两个一维数组 prev 和 curr，长度为 word2 的长度加一。
  2. 初始化 prev 数组为 [0, 1, 2, ..., word2.length]，表示将空字符串转换为 word2 的操作次数。
  3. 遍历字符串 word1 的每个字符，同时更新 curr 数组：
    • 对于每个字符，先将 curr[0] 设为 i+1，表示将 word1 的前 i 个字符转换为空字符串的操作次数。
    • 对于每个字符，再遍历字符串 word2 的每个字符，根据状态转移方程更新 curr 数组的值。
  4. 最终的编辑距离即为 curr[word2.length]。
int minDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    
    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[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
            }
        }
    }
    
    return dp[m][n];
}

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-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
            }
        }
    }
    
    return dp[m][n];
}

func minDistance(word1 string, word2 string) int {
    m := len(word1)
    n := len(word2)
    
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }
    
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
            }
        }
    }
    
    return dp[m][n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def minDistance(word1, word2):
    m = len(word1)
    n = len(word2)
    
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    for i in range(m+1):
        dp[i][0] = i
    
    for j in range(n+1):
        dp[0][j] = j
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
    
    return dp[m][n]

function minDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    
    const dp = Array.from({ length: m+1 }, () => Array(n+1).fill(0));
    
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i-1] === word2[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-1][j], dp[i][j-1])) + 1;
            }
        }
    }
    
    return dp[m][n];
}
取自“https://www.aigetting.com/index.php?title=题目:编辑距离&oldid=2095”