Medium

题目描述

给定两个字符串 word1 和 word2，返回使 word1 和 word2 相同所需的最小步数。

每一步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea"，第二步将 "eat" 变为 "ea"。

示例 2：

输入: word1 = "leetcode", word2 = "etco"
输出: 4

提示：

  • 1 <= word1.length, word2.length <= 500
  • word1 和 word2 只包含小写英文字母。

解题思路

这道题本质上是求两个字符串的**最长公共子序列（LCS）**问题的变形。

思路分析

要使两个字符串相同，我们需要删除不相同的字符，保留相同的字符。最优策略是保留最长公共子序列，然后删除其余字符。

设两个字符串长度分别为 m 和 n，最长公共子序列长度为 lcs，那么：

  • word1 需要删除 m - lcs 个字符
  • word2 需要删除 n - lcs 个字符
  • 总删除步数 = (m - lcs) + (n - lcs) = m + n - 2 * lcs

解法选择

方法一：直接 DP 直接定义 dp[i][j] 表示使 word1[0:i] 和 word2[0:j] 相同所需的最小删除次数。

方法二：LCS + 计算（推荐） 先求最长公共子序列长度，再用公式计算总删除次数。代码更直观易懂。

状态转移

对于 LCS 方法：

  • dp[i][j] 表示 word1[0:i-1] 和 word2[0:j-1] 的最长公共子序列长度
  • 如果 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
  • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

代码实现

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        // 求最长公共子序列长度
        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] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        return m + n - 2 * dp[m][n];
    }
};

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 求最长公共子序列长度
        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] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        return m + n - 2 * dp[m][n]

public class Solution {
    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 = 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] + 1;
                } else {
                    dp[i,j] = Math.Max(dp[i-1,j], dp[i,j-1]);
                }
            }
        }
        
        return m + n - 2 * dp[m,n];
    }
}

var minDistance = function(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    
    // dp[i][j] represents LCS length of word1[0..i-1] and word2[0..j-1]
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    // Fill the dp table to find LCS
    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] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // Total deletions = (m - lcs) + (n - lcs) = m + n - 2 * lcs
    return m + n - 2 * dp[m][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历 m×n 的二维数组，其中 m 和 n 分别为两个字符串的长度
空间复杂度O(m × n)需要创建 (m+1)×(n+1) 的二维 DP 数组

相关题目