LeetCode72——Edit Distance

约定不等于承诺〃 2022-08-10 06:16 205阅读 0赞

**十一月太忙，好一阵没写博客没刷题，现在事情忙完了，生活规律要逐步走入正轨。**

\--------------------------------------------------------------------------------------------------

LeetCode72——Edit Distance

动态规划一直不是我的强项，但是这道题恰好不知道在哪里见到过。

首先说说动归方程：

dp\[i\]\[j\]表示从word1的前i个字符( 0 ~ i - 1 )到word2的前j个字符( 0 ~ j - 1)的编辑过程中，需要的最少步数，那么：

如果 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，简单说明

假设word1的前i+1（下标从0~i）的子串为 "abcde"

假设word2的前j+1（下标从0~j）的子串为 "abcddgf"

现在word1\[i\] != word2\[j\] 即 'e' != 'f'

那么我们应当如何编辑？

分为三种情况：

1.从子串"abcd"编辑到子串"abcddg" 经过编辑后，word1变为"abcddge" （步数为dp\[i-1\]\[j-1\]）

此时从word1编辑到word2只需要将'e'替换为'f' （步数为1）

加起来就是：dp\[i-1\]\[j-1\] + 1

2.从子串"abcd"编辑到子串"abcddgf"经过编辑后word1变成"abcddgfe" （步数为dp\[i-1\]\[j\]）

此时从word1编辑到word2只需要将'e'删掉 （步数为1）

加起来就是：dp\[i-1\]\[j\] + 1

3.从子串"abcde"编辑到子串"abcddg"经过编辑后word1变成"abcddg" （步数为dp\[i\]\[j-1\]）

此时从word1编辑到word2只需要插入字符'f'

加起来就是：dp\[i\]\[j-1\] + 1

上述三种情况，事实上就完成了 Insert，Delete，Replace 三个操作

这三个操作需要的步数都是1，只需要比较上一次编辑（三种情况）到当前状态（只需要这三个操作之一就可以完成编辑）所需要的最小步数即可。

代码：

class Solution {
    private:
    	int myMin(int a, int b, int c)
    	{
    		if (b < a)
    			a = b;
    		if (c < a)
    			a = c;
    		return a;
    	}
    public:
    	int minDistance(string word1, string word2) {
    		int len1 = word1.length();
    		int len2 = word2.length();
    		vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1));//dp
    		//初始化
    		for (int i = 0; i <= len1; i++)
    		{
    			dp[i][0] = i;
    		}
    		for (int j = 1; j <= len2; j++)
    		{
    			dp[0][j] = j;
    		}
    
    		//if  word1[i]==word2[j]
    		//dp[i][j]  =  dp[i-1][j-1]
    		//
    		//
    		for (int i = 1; i <= len1; i++)
    		{
    			for (int j = 1; j <= len2; j++)
    			{
    				if (word1[i-1] == word2[j-1])
    				{
    					dp[i][j] = dp[i - 1][j - 1];
    				}
    				else
    				{
    					dp[i][j] = myMin(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
    				}
    			}
    		}
    		return dp[len1][len2];
    	}
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，205人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 72. Edit Distance (动归)

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

港控/mmm°/ 2024年04月17日 23:45/ 0 赞/ 72 阅读

相关 LeetCode72——Edit Distance

十一月太忙，好一阵没写博客没刷题，现在事情忙完了，生活规律要逐步走入正轨。 \------------------------------------------------

约定不等于承诺〃/ 2022年08月10日 06:16/ 0 赞/ 206 阅读

相关 LeetCode - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert wo

左手的ㄟ右手/ 2022年08月04日 12:45/ 0 赞/ 58 阅读

相关 leetcode Edit Distance

题目 Given two words word1 and word2, find the minimum number of steps required to conv

约定不等于承诺〃/ 2022年08月01日 11:18/ 0 赞/ 176 阅读

相关 leetcode 72. Edit Distance DP动态规划 + 编辑距离

Given two words word1 and word2, find the minimum number of steps required to convert wo

妖狐艹你老母/ 2022年06月08日 01:24/ 0 赞/ 242 阅读

相关 LeetCode 72.Edit Distance (编辑距离)

题目：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作： 1. 插入一个字

墨蓝/ 2022年04月15日 04:30/ 0 赞/ 230 阅读

相关 LeetCode：72. Edit Distance(编辑的最小步数)

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

「爱情、让人受尽委屈。」/ 2022年04月05日 13:20/ 0 赞/ 174 阅读

相关 #72 Edit Distance——Top 100 Liked Questions

Given two words word1 and word2, find the minimum number of operations required to conve

妖狐艹你老母/ 2022年01月29日 03:09/ 0 赞/ 229 阅读

相关 leetcode--Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert wo

短命女/ 2021年10月25日 12:40/ 0 赞/ 260 阅读

相关 LeetCode : 72. Edit Distance 编辑距离

试题 Given two words word1 and word2, find the minimum number of operations required to

偏执的太偏执、/ 2021年09月18日 18:06/ 0 赞/ 372 阅读