兩個字符串的刪除操作

給定兩個單詞?word1?和?word2，找到使得?word1?和?word2?相同所需的最小步數，每步可以刪除任意一個字符串中的一個字符。

示例 1:

輸入: "sea", "eat"

輸出: 2

解釋: 第一步將"sea"變為"ea"，第二步將"eat"變為"ea"

說明:

給定單詞的長度不超過500。

給定單詞中的字符只含有小寫字母。

思路

首先求出最長公共子序列，然后字符串的長度減去最長公共子序列的長度就是要刪除的長度。

c[i,j]表示：(x1,x2....xi) 和 (y1,y2...yj) 的最長公共子序列的長度。

?

1 class Solution { 2 public int minDistance(String word1, String word2) { 3 int n=word1.length(); 4 int m=word2.length(); 5 int[][] dp=new int[n+1][m+1]; 6 for(int i=0;i<=n;i++) dp[i][0]=0; 7 for(int j=0;j<=m;j++) dp[0][j]=0; 8 for(int i=1;i<=n;i++){ 9 for(int j=1;j<=m;j++){ 10 if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1; 11 else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); 12 } 13 } 14 return word1.length()+word2.length()-2*dp[n][m]; 15 } 16 }

?

?

?

轉載于:https://www.cnblogs.com/kexinxin/p/10381394.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Leetcode 583.两个字符串的删除操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。