数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学通过删除字符串A两端字符并在任意位置重新插入字符，将其转换为字符串B
字符串的变位词是指包含与另一个字符串完全相同的字符的字符串，但字符顺序可能与原始字符串不同，因此我们称这两个字符串互为变位词。这里我们给出了两个互为变位词的字符串，第一个和第二个。我们的任务是最小化操作次数，以使第一个字符串与第二个字符串相同。
一个操作是指我们可以从第一个字符串的开头或结尾删除一个字符，然后将其重新插入到任意位置。
示例
输入
First: "hello", Second: "ohlle"
输出
3
解释
在这里，我们执行最少的操作以使第一个字符串与第二个字符串相同：
从第一个字符串中删除最后一个字符并将其放在索引0处，“ohell”
再次，从更新后的第一个字符串中删除最后一个字符并将其放在索引2处，“ohlel”
再次，从更新后的第一个字符串中删除最后一个字符并将其放在索引3处，“ohlle”
输入
First: "world", Second: "world"
输出
0
解释
因为这里第一个字符串和第二个字符串彼此相等。
使用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 是给定字符串的大小。
使用数组代替二维矩阵的上述方法的高效版本
这与上述方法相同，唯一的区别是这里我们使用线性数组而不是二维矩阵，这将为我们提供更好的空间复杂度。这将降低空间复杂度，因为我们将修剪不需要的结果并将其替换为新计算的值。
示例
让我们看看下面的代码，以便更好地理解上述方法。
#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 转换为字符串 B。我们已经实现了两种方法来解决这个问题。方法是使用 LCS 概念的具有二维矩阵的动态方法，以及使用数组代替二维矩阵的第一种方法的高效版本。
65 次浏览
