在C ++中删除两个字符串的操作

假设我们有两个单词w1和w2，我们必须找到使w1和w2相同所需的最小步骤数，其中在每个步骤中我们都可以删除任一字符串中的一个字符。因此，如果输入像“ sea”和“ eat”，那么输出将为2，因为我们需要从w1中删除“ s”，所以它将为“ ea”，并从w2中从“ eat”中删除“ t”。然后它们是相同的。

为了解决这个问题，我们将按照以下步骤

• n：= s1的大小，m：= s2的大小

• 在字符串s1和s2之前添加一个空格，然后相应地更新s1和s2

• 制作一张大小为（n + 1）x（m + 1）的桌子

• 对于我：= 1到m

• dp [0，i]：= dp [0，i-1] + 1

• 对于我：= 1到n

• dp [i，0]：= dp [i – 1，0] + 1

• 对于我在1到n范围内

• 如果s1 [i] = s2 [j]

• 否则dp [i，j] = dp [i – 1，j] + 1和dp [i，j-1] + 1的最小值

• dp [i，j]：= dp [i – 1，j-1]

• 对于1到m范围内的j

• 返回dp [n，m]

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minDistance(string s1, string s2) {
      int n = s1.size();
      int m = s2.size();
      s1 = " " + s1;
      s2 = " " + s2;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= m; i++){
         dp[0][i] = dp[0][i - 1] + 1;
      }
      for(int i = 1; i <= n; i++){
         dp[i][0] = dp[i - 1][0] + 1;
      }
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s1[i] == s2[j]){
               dp[i][j] = dp[i - 1][j - 1];
            }
            else{
               dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1};
   cout << (ob.minDistance("sea", "eat"));
}

输入值

"sea"
"eat"

输出结果

2