C++ 将字符串A转换为B，通过删除字符的端点并重新插入到任意位置

一个字符串的字谜意味着该字符串包含与另一个字符串完全相同的字符，字符的顺序可能与原始字符串不同，所以我们称这两个字符串互为字谜。这里我们给出了两个字符串first和second，它们互为字谜。我们的任务是将第一个字符串变成第二个字符串的操作数量最小。

一种操作是我们可以从第一个字符串的开头或末尾删除一个字符，并将其重新插入到任意位置。

示例

输入1

First: "hello",
Second: "ohlle"

输出

3

解释

这里我们执行最少的操作来使第一个字符串成为第二个字符串−

• 从第一个字符串中删除最后一个字符并放在索引0中，”ohell”

• 再次从更新后的第一个字符串中删除最后一个字符并放在索引2中，”ohlel”

• 再次从更新后的第一个字符串中删除最后一个字符并放在索引3中，”ohlle”

输入2

First: "world",
Second: "world"

输出

0

解释

在这里，第一个字符串和第二个字符串都相等。

使用LCS概念的动态方法

我们将使用最长公共子序列（LCS）的概念来解决这个问题，LCS是动态规划中非常流行的问题。

示例

让我们看一下下面的代码，以更好地理解上述方法。

#include <bits/stdc++.h>
using namespace std;

// Create a function to minimize the count of operations
int minimizeCountOfOperations(string First, string Second){
   // Create an 2d matrix to maintain the longest continous length of first string that is part of the string second subsequence
   int t[1001][1001];
   // Variable maxlen store the maximum value of 2d matrix d 
   int maxlen = 0;
   for (int i = 0; i <= First.size(); i++) {
      for (int j = 0; j <= Second.size(); j++) {
         t[i][j] = 0;
         if (i && j) {             
            // if the sufix of first string is part of both second string upto j and also j-1 
            t[i][j] = t[i][j - 1];                
            // last charcter of both the string equal, then suffix of first string upto i-1 is part of second string upto j-1
            if (First[i - 1] == Second[j - 1]) {
               t[i][j] = max(t[i][j],1 + t[i - 1][j - 1]);
               maxlen = max(maxlen, t[i][j]);
            }
         }
      }
   } 
   return First.size() - maxlen;
}
int main(){
   string First = "hello";
   string Second = "ohlle";    
   int minCount = minimizeCountOfOperations(First, Second);
   cout << "Count of Minimum Operation needed to transform first string into second string is: " << minCount;
   return 0;
}

输出

Count of Minimum Operation needed to transform first string into second string is: 3

时间和空间复杂度

上述代码的时间复杂度为O(N^2)。

上述代码的空间复杂度为O(N^2)，因为我们使用一个二维矩阵来存储结果。

这里N表示给定字符串的大小。

采用数组而不是2D矩阵的高效版本

这与上述方法相同，唯一的区别是我们使用一个线性数组而不是二维矩阵，这将提供更好的空间复杂度。通过去除不需要的结果并用新计算出的值替换它，这将减少空间复杂度。

示例

为了更好地理解上述方法，请查看下面的代码。

#include <bits/stdc++.h>
using namespace std;

// Create a function to minimize the count of operations
int minimizeCountOfOperations(string First, string Second){
   // Create an array to maintain the longest continous length of first string that is part of the string second subsequence and assign it 0
   int t[1001] = {0}; 
   // Variable maxlen store the maximum value of 2d matrix d
   int maxlen = 0; 
   for (int i = 1; i <= First.size(); i++) {
      int previousVal = 0;
      for (int j = 1; j <= Second.size(); j++) {            
         int store = t[j];
         t[j] =t[j-1];            
         if(First[i - 1] == Second[j - 1])
            t[j] = max(t[j], previousVal+1);
         else 
            t[j] = max(t[j], 0);               
            previousVal = store;
         maxlen = max(maxlen, t[j]);
      }
   }    
   return First.size() - maxlen;
}
int main(){
   string First = "hello";
   string Second = "ohlle";
   int minCount = minimizeCountOfOperations(First, Second);
   cout << "Count of Minimum Operation needed to transform first string into second string is: " << minCount;
   return 0;
}

输出

Count of Minimum Operation needed to transform first string into second string is: 3

时间和空间复杂度

以上代码的时间复杂度为O(N^2)。

以上代码的空间复杂度为O(N)，因为我们使用了数组。

其中N是给定字符串的大小。

结论

在本教程中，我们实现了一个C++程序，通过删除字符串A的字符并将其重新插入到任意位置，从而将字符串A转换为字符串B。我们实现了两种方法来解决这个问题。方法是使用LCS的概念和2D矩阵的动态方法，第二种方法是使用数组而不是2D矩阵的第一种方法的高效版本。