小工具知识网

当前位置: 首页 > 行业知识 > 代码随想录算法训练营第五十五天|583. 两个字符串的删除操作、72. 编辑距离。

行业知识

代码随想录算法训练营第五十五天|583. 两个字符串的删除操作、72. 编辑距离。

2026-11-21 07:14:43 来源:互联网转载

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

题���链接:两个字符串的删除操作

()

题目描述:

给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。

()

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

解题思路:

1、确定dp数组(dp table)以及下标的含义

dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。

这里dp数组的定义有点点绕,大家要撸清思路。

2、确定递推公式

当word1[i - 1] 与 word2[j - 1]相同的时候

当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况:

情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1

情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1

情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值,所以当word1[i - 1] 与 word2[j - 1]不相同的时候,递推公式:dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2,所以递推公式可简化为:dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

这里可能不少录友有点迷糊,从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1],dp[i][j-1] 本来就不考虑 word2[j - 1]了,那么我在删 word1[i - 1],是不是就达到两个元素都删除的效果,即 dp[i][j-1] + 1。

3、dp数组如何初始化

从递推公式中,可以看出来,dp[i][0] 和 dp[0][j]是一定要初始化的。

dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i。

dp[0][j]的话同理

代码实现:

class Solution {    public int minDistance(String word1, String word2) {        int len1 = word1.length();        int len2 = word2.length();        int[][] dp = new int[len1 + 1][len2 + 1];        for (int i = 1; i             for (int j = 1; 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]);                }            }        }        return len1 + len2 - dp[len1][len2] * 2;    }}    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             dp[i][0] = i;        }        for (int j = 1; j             dp[0][j] = j;        }        for (int i = 1; i             for (int j = 1; j                 // 因为dp数组有效位从1开始                // 所以当前遍历到的字符串的位置为i-1 | j-1                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                    dp[i][j] = dp[i - 1][j - 1];                } else {                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;                }            }        }        return dp[m][n];    }}

上一篇:如何重新安装edge?

下一篇:日志服务器怎么获得?