LeetCode 583. 两个字符串的删除操作

Categories:

题目描述
思路分析
1. 解法一：最长公共子序列（推荐）
相似题目

题目描述

✅ 583. 两个字符串的删除操作

思路分析

解法一：最长公共子序列（推荐）

核心思路：

删除操作等价于保留两个字符串的最长公共子序列。

设 LCS 长度为 lcs，则最少删除次数为 m + n - 2 * lcs。

使用经典二维 DP 计算 LCS。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示字符串长度。

空间复杂度：O(m * n)，用于 DP 表。

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 = 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] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        int lcs = dp[m][n];
        return m + n - 2 * lcs;
    }
}

func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	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] + 1
			} else {
				if dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}

	lcs := dp[m][n]
	return m + n - 2*lcs
}

相似题目

题目	难度	考察点
1143. 最长公共子序列	中等	动态规划
72. 编辑距离	困难	动态规划
712. 两个字符串的最小 ASCII 删除和	中等	动态规划
392. 判断子序列	简单	双指针
1092. 最短公共超序列	困难	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/60502955