leetcode 72. 编辑距离

悠悠 2021-12-21 01:27 379阅读 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 条评论，379人围观）

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

相关阅读

相关 LeetCode-72. 编辑距离

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

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

相关 leetcode 72. 编辑距离

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

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

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

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

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

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

相关 72. 编辑距离

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

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

相关 Leetcode 72. 编辑距离

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

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

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

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

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

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