leetcode 72. 编辑距离

悠悠 2021-12-21 01:27 297阅读 0赞

![1588437-20190516145616651-338815526.png][]

/*****
    定义状态：
    DP[i][j]其中i表示word1前i个字符，j表示Word2前i个字符
    DP[i][j]表示单词1前i个字符匹配单词2前j个字符，最少变换次数；
    状态转移：
    for i:[0,m]
        for j:[0,n]
        if(word1[i-1]==word2[j-1])
            DP[i][j]=DP[i-1][j-1];
        else
            DP[i][j]=min(DP[i-1][j],DP[i][j-1],DP[i-1][j-1])+1;
    return DP[m][n];
    
    ******/
    
    
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m=word1.size(),n=word2.size();
            vector<vector<int> > DP(m+1,vector(n+1,0));
            //初始化
            for(int i=0;i<=m;i++){
                DP[i][0]=i;
            }
            for(int j=0;j<=n;j++){
                DP[0][j]=j;
            }
            //状态转移
            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];
                    else
                        DP[i][j]=min(min(DP[i-1][j],DP[i][j-1]),DP[i-1][j-1])+1;
                }
            }
            return DP[m][n];
        }
    };

转载于:https://www.cnblogs.com/joelwang/p/10875673.html

[1588437-20190516145616651-338815526.png]: /images/20211221/0148f88ab3084f0bbcbc756487164816.png

发表评论取消回复

表情：

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

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

相关阅读

相关 72. 编辑距离——【Leetcode每日一题】

72. 编辑距离给你两个单词 `word1` 和 `word2`，请返回将 `word1` 转换成 `word2` 所使用的最少操作数。你可以对一个单词进行如下

柔情只为你懂/ 2024年03月26日 00:08/ 0 赞/ 18 阅读

相关 leetcode72 编辑距离

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

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

相关 72. 编辑距离

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

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

相关 Leetcode 72. 编辑距离

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

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

相关 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 赞/ 187 阅读

相关 LeetCode072:编辑距离

实验平台：[LeetCode][] 代码地址：[my github][] 题目描述： ![这里写图片描述][70] 示例： ![这里写图片描述][70 1]

た入场券/ 2022年05月18日 03:56/ 0 赞/ 167 阅读

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

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

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

相关 leetcode 72. 编辑距离

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

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

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

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

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

相关 ✔[72]编辑距离

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

亦凉/ 2021年06月22日 15:38/ 0 赞/ 454 阅读