专栏首页算法修养LeetCode 72. Edit Distance

LeetCode 72. Edit Distance

简单动态规划

class Solution {
public:
    int dp[1005][1005];
    int minDistance(string word1, string word2) {
        
        int len1=word1.length();
        int len2=word2.length();
        
        if(len1==0)
            return len2;
        if(len2==0)
            return len1;
        
        for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                dp[i][j]=99999;
                if(i==0&&j==0)
                {
                    if(word1[i]==word2[j])
                    {
                        dp[i][j]=0;
                    }
                    else
                        dp[i][j]=1;
                    
                    continue;
                }
                
                if(i>0)
                    dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
                if(j>0)
                    dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
                if(i>0&&j>0)
                    dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
                
                if(word1[i]==word2[j])
                {
                    if(i>0&&j>0)
                        dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
                    if(i==0)
                    {
                        dp[i][j]=min(dp[i][j],j);
                    }
                    if(j==0)
                        dp[i][j]=min(dp[i][j],i);
                }
                
            }
        }
        
        return dp[len1-1][len2-1];
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一道网易面试编程题

    一条长为n的路,需要用路灯点亮,其中"."表示需要点亮的位置,"X"表示无需点亮的位置,假设灯立在i处,则它可以点亮i-1,i,i+1三个位置,问至少需要多少灯...

    ShenduCC
  • POJ-放苹果(DP)

    放苹果 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 29074 ...

    ShenduCC
  • LeetCode 1595 Minimum Cost to Connect Two Groups of Points (动态规划)

    题解: 动态规划,用二进制压缩状态,注意分析几种情况,就能推出来正确的状态转移方程。

    ShenduCC
  • 利用python代码求三角形最小路径和

    哈喽!同学们,今天和大家分享一下,利用Python代码求三角形最小路径和!给定一个三角形,每一步只能移动到下一行中相邻的结点上,求出自顶向下的最小路径和。

    小小科
  • LeetCode 91,点赞和反对五五开,这题是好是坏由你来评判

    今天是LeetCode专题的第57篇文章,我们一起来看看LeetCode第91题,解码方法(Decode ways)。

    TechFlow-承志
  • 递归,递推以及动态规划总结

    在我的映像里面,当初第一次结束DP的时候,总感觉跟递归还是递归好像!以至于我混淆了他们。

    用户7727433
  • LeetCode 刷题记录(二)

    如果执行环境只能存储得下 32 位有符号整数,那么其数值范围为 (最高位为符号位),翻转时如果溢出请返回 0。

    口仆
  • Python|利用代码求三角形最小路径和

    题目:给定一个三角形,每一步只能移动到下一行中相邻的结点上,求出自顶向下的最小路径和。

    算法与编程之美
  • 每日算法系列【LeetCode 115】不同的子序列

    一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 ...

    godweiyang
  • Leetcode 91 Decode Ways

    A message containing letters from A-Z is being encoded to numbers using the fol...

    triplebee

扫码关注云+社区

领取腾讯云代金券