Leetcode 72 Edit Distance

本文主要是介绍Leetcode 72 Edit Distance，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character
Example 1:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
Example 2:

Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)

中文：
给你两个字符串word1和word2，限制你使用三种手段，即插入一个字符、删除一个字符和替换一个字符，使得将word1变换为word2。

代码：

class Solution {
public:int min3(int x,int y,int z){return min(min(x,y),min(y,z));}int dp[1001][1001];int minDistance(string word1, string word2) {if(word2.size()==0)return word1.size();if(word1.size()==0)return word2.size();memset(dp,0,sizeof(dp));for(int i=1;i<=word1.size();i++)dp[i][0]=i;for(int j=1;j<=word2.size();j++)dp[0][j]=j;for(int i=1;i<=word1.size();i++){for(int j=1;j<=word2.size();j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min3(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;}}return dp[word1.size()][word2.size()];}
};

思路：

中规中矩的一道动态规划题目，由于是要将word1变换成word2，那么在考虑问题的时候只能操作word1，而不能操作word2，这一点需要在状态转移的过程当中体现出来。

设置状态$dp[i][j]$表示将word1的前i个字符变换成word2的前j个字符最少需要的步骤是多少？

此题可以先按照i>j或者i<j分开考虑，其实无论是word1长还是word2长，状态转移的方式是一样的。

题目中给了三种操作方式，分别是删除、插入、替换。

考虑状态转移的过程

如果 $word1[i]==word2[j]$
那么
$dp[i][j]=dp[i-1][j-1]$
表示word1第i个字符和word2第j个字符相同，不需要进行操作，直接将$dp[i-1][j-1]$的状态转移过来即可。

如果$word1[i]!=word2[j]$
那么有三种可以操作的状态
$$dp[i][j]=min3(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)$$

其中
$dp[i-1][j-1]+1$ 表示将word1的第i个字符替换为word2的第j个字符

$dp[i-1][j]+1$ 表示将word1的第i个字符删除

$dp[i][j-1]+1$ 表示在word1后面插入一个字符，这个字符与word2的第j个字符相同

最后注意初始化的值即可

这篇关于Leetcode 72 Edit Distance的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---