leetcode 72. 编辑距离

雨点打透心脏的1/2处 2023-07-03 02:47 14阅读 0赞

思路：

dp\[i\]\[j\]表示以word1\[i\]结尾的字符串，变为以word2\[j\]结尾的字符，需要的最少编辑次数。

若word1\[i\]==word2\[j\] ，那么不需要任何操作dp\[i\]\[j\]=dp\[i-1\]\[j-1\]

若不等，则有三种方法

1. 删除一个字符, 即dp\[i\]\[j\]=dp\[i-1\]\[j\] +1（意思是，删除掉word1\[i\]以后，两个字符串相同，那么也就等价于word1\[i-1\]与word2\[j\]）

2. 替换。这个比较容易理解，替换一个，那么前面的word1\[i-1\]和word2\[j-1\]一定相同。dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1

3. 插入，这个比较难理解。在word1\[i\]后面插入一个字符，其实等价于把word\[j\]删除。即dp\[i\]\[j\]=dp\[i\]\[j-1\]。也就是word1\[i\]之前的字符，要和word2\[j-1\]以前的字符相同。

这三种方法取最小值即可。

写代码的时候，要注意初始化。

class Solution {
    public:
        int minDistance(string word1, string word2) {
            int n1=word1.size();
            int n2=word2.size();
            int dp[n1+3][n2+3];
            memset(dp,0,sizeof(dp));
            for(int j=1;j<=n2;j++)
            {
                dp[0][j]=j;
            }
            for(int i=1;i<=n1;i++)
            {
                dp[i][0]=i;
            }
            for(int i=1;i<=n1;i++)
            {
                for(int j=1;j<=n2;j++)
                {
                    if(word2[j-1]==word1[i-1])
                    {
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else
                    {
                        dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                    }
                }
            }
            return dp[n1][n2];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-72. 编辑距离

目录动态规划题目来源 [72. 编辑距离][72.] 动态规划 1.确定dp数组（dp table）以及下标的含义 dp\[i\]\[j\

红太狼/ 2024年03月24日 12:49/ 0 赞/ 57 阅读

相关 leetcode 72. 编辑距离

思路： dp\[i\]\[j\]表示以word1\[i\]结尾的字符串，变为以word2\[j\]结尾的字符，需要的最少编辑次数。若word1\[i\]==word2\[

雨点打透心脏的1/2处/ 2023年07月03日 02:47/ 0 赞/ 15 阅读

相关 leetcode72 编辑距离

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

淩亂°似流年/ 2023年06月20日 06:18/ 0 赞/ 27 阅读

相关 leetcode72 编辑距离

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

阳光穿透心脏的1/2处/ 2023年06月16日 10:47/ 0 赞/ 138 阅读

相关 LeetCode72. 编辑距离【动态规划】

难度：困难题目描述： > 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。 > > 你可以对一个单词进行

Love The Way You Lie/ 2023年01月22日 09:53/ 0 赞/ 30 阅读

相关 72. 编辑距离

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

拼搏现实的明天。/ 2022年10月10日 01:51/ 0 赞/ 179 阅读

相关 Leetcode 72. 编辑距离

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

叁歲伎倆/ 2022年09月02日 13:55/ 0 赞/ 168 阅读

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

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

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

相关 leetcode 72. 编辑距离

![1588437-20190516145616651-338815526.png][] / 定义状态： DP[i][j]其中i表示word1前i个字

悠悠/ 2021年12月21日 01:27/ 0 赞/ 380 阅读

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

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

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