本文共 1144 字，大约阅读时间需要 3 分钟。

1. 题目

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：输入: "sea", "eat"输出: 2解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea" 提示：给定单词的长度不超过500。给定单词中的字符只含有小写字母。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

class Solution {
   public:    int minDistance(string word1, string word2) {
       	int n1 = word1.size(), n2 = word2.size(), i, j;    	if(n1==0 || n2==0)    		return max(n1,n2);    	vector
   
    
     > dp(n1+1,vector
     
      (n2+1,INT_MAX));    	for(i = 0; i <= n1; ++i)    		dp[i][0] = i;//第二字符串长度为0，需要删除第一个字符串多少个字符    	for(i = 0; i <= n2; ++i)    		dp[0][i] = i;    	for(i = 1; i <= n1; ++i)    	{
       		for(j = 1; j <= n2; ++j)    		{
       			if(word1[i-1]==word2[j-1])//w1第i个字符和 w2第j个字符相等    				dp[i][j] = dp[i-1][j-1];//需要删除的最少字符等于前面的    			else    			{
       				dp[i][j] = 1+min(dp[i][j-1],dp[i-1][j]);    				//不相等    				//可以有两种方式，删除一个 j，然后次数+1，dp[i][j-1]+1    				//或者删除一个 i，次数+1，dp[i-1][j]+1    				//其实还有一个删除i,j，次数+2，dp[i-1][j-1]+2，不可能次数最少    			}    		}    	}    	return dp[n1][n2];    }};
     
    
   

40 ms 12.1 MB

转载地址：https://michael.blog.csdn.net/article/details/106009461 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！