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

妖狐艹你老母 2022-06-08 01:24 193阅读 0赞

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2。 (each operation is counted as 1 step。)

You have the following 3 operations permitted on a word:

a) Insert a character  
b) Delete a character  
c) Replace a character

这个就是经典的编辑距离的问题，就是经典的DP解决，具体为什么这么做就不多说了，我这里就简单的描述一下DP的过程。

用dp\[i\]\[j\]表示从word1\[i\]变为word2\[j\]所需要的最少步骤。那么主要分为一下几种情况处理：  
**1) 替换代价：**若word1\[i\]=word2\[j\] , 则只需把word1\[0…i-1\]变为word2\[0…j-1\]，equalCost = dp\[i-1\]\[j-1\]，否者equalCost = dp\[i-1\]\[j-1\]+1；

**2) 插入代价：**若在word1\[i\]插入某字符是word1到word2\[的最小改动，insertCost= dp\[i\]\[j-1\] + 1;

**3) 删除代价：**若删除word1\[i\]是word1到word2的最小改动，则deleteCost = dp\[i-1\]\[j\] + 1。

**最后dp\[i\]\[j\]是替换代价、插入代价和删除代价的最小值。**

代码如下：

public class Solution 
    {
        /*
         * http://www.bubuko.com/infodetail-644271.html
         * 
         * 这个题吧比较难，动态规划DP解决                                                   
         * */
    
        public int minDistance(String word1, String word2) 
        {
            if(word1==null || word1.length()<=0)
                return word2.length();
            if(word2==null || word2.length()<=0)
                return word1.length();
    
            int [][]dp=new int[word1.length()+1][word2.length()+1];
            for(int i=0;i<dp.length;i++)
                dp[i][0]=i;
            for(int i=0;i<dp[0].length;i++)
                dp[0][i]=i;
    
    /*      用dp[i][j]表示从word1[i]变为word2[j]所需要的最少步骤。
    
            1) 匹配：若word1[i]=word2[j] , 则只需把word1[0...i-1]变为word2[0...j-1]
                    即可. ==> dp[i][j] = dp[i-1][j-1].
    
            2) 替换：把word1[i]替换word2[j]是从word1到word2的最小改动，
            则 先把word1[0...i-1]以最小代价变为word2[0...j-1]，再替换. ==> dp[i][j] = dp[i-1][j-1] + 1.
    
            3) 插入：若在word1[i]插入某字符是word1到word2[的最小改动，
                                              则先把word1[0...i]以最小代价变为word2[0...j-1]，在此基础上加上word2[j], ==> dp[i][j] = dp[i][j-1] + 1.
    
            4) 删除：若删除word1[i]是word1到word2的最小改动，
            则先把word1[0...i-1]以最小代价变为word2[0...j], 再删除word1[j]即可，
            dp[i][j] = dp[i-1][j] + 1.*/
    
              for(int i=1;i<=word1.length();i++)
              {
                  for(int j=1;j<=word2.length();j++)
                  {
                      int addA=dp[i][j-1]+1;
                      int deleteA=dp[i-1][j]+1;
                      int eqA=0;
                      if(word1.charAt(i-1)==word2.charAt(j-1))
                          eqA=dp[i-1][j-1];
                      else
                          eqA=dp[i-1][j-1]+1;
                      dp[i][j]=Math.min(addA, Math.min(deleteA, eqA)); 
                  }
              }
            return dp[word1.length()][word2.length()];
        }
    }

下面是C++的做法，就是一个很经典但是也很难想的DP动态规划的做法

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    
    using namespace std;
    
    class Solution
    {
    public:
        int minDistance(string word1, string word2) 
        {
            int m = word1.length(), n = word2.length();
            vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
            for (int i = 1; i <= m; i++)
                dp[i][0] = i;
            for (int j = 1; 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(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
                }
            }
            return dp[m][n];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode 72. Edit Distance (动归)

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

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

相关 LeetCode72——Edit Distance

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

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

相关编辑距离Edit distance

http://[blog.csdn.net/pipisorry/article/details/46383947][blog.csdn.net_pipisorry_articl

谁借莪１个温暖的怀抱￠/ 2022年08月05日 04:29/ 0 赞/ 283 阅读

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

相关 [Leetcode][python]Edit Distance/编辑距离

题目大意求两个字符串之间的最短编辑距离，即原来的字符串至少要经过多少次操作才能够变成目标字符串，操作包括删除一个字符、插入一个字符、更新一个字符。解题思路动

电玩女神/ 2022年06月07日 10:10/ 0 赞/ 144 阅读

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

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

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

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

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

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

相关【Leetcode】72. Edit Distance（动态规划）(2019拼多多笔试)（重点）

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

曾经终败给现在/ 2022年02月25日 11:28/ 0 赞/ 128 阅读

相关 leetcode 72. 编辑距离

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

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

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

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

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