在这个问题中，我们需要使用str1的子序列来构造str2。为了解决这个问题，我们可以找到str1的子序列，使其能够覆盖最大长度为str2的子串。在这里，我们将学习两种不同的方法来解决问题。
问题陈述 – 我们给出了两个不同长度的字符串：str1 和 str2。我们需要按照以下条件从 str1 构造 str2。
从 str1 中选取任何子序列，并将其附加到新字符串（最初为空）。
我们需要返回构造str2所需的最少操作数，如果无法构造str2，则打印-1。
输入– str1 =“acd”，str2 =“adc”
输出– 2
说明
str1 中的第一个子序列是“ad”。所以，我们的字符串可以是“ad”。
之后，我们可以从 str1 中获取“c”子序列并将其附加到“ad”以使其成为“adc”。
输入– str1 = "adcb", str2 = "abdca"
输出– 3
说明
第一个子序列是 str1 中的“ab”。
之后，我们可以获取“dc”字符串，结果字符串将是“abdc”
接下来，我们可以使用“a”子序列来生成最终的字符串“abdca”。
在这种方法中，我们将迭代 str1 以查找多个子序列并将其附加到结果字符串中。
定义长度为 26 的“arr”数组，并将所有元素初始化为 0，以存储字符在 str1 中的存在。
迭代str1，根据字符的ASCII值更新数组元素的值
定义“last”变量并使用 -1 进行初始化以跟踪最后访问的元素。另外，定义“cnt”变量并将其初始化为 0 以存储操作计数。
开始使用循环遍历 str2。
如果当前字符不在str1中，则返回-1。
使用“last + 1”值初始化“j”变量。
使用while循环进行迭代，直到j的值小于len，且str1[j]不等于字符
如果‘j’的值大于‘len’，我们遍历‘str1’。增加 'cnt' 变量的值，将 'last' 初始化为 -1，因为我们需要再次遍历 'str1'，将 'I' 的值减少 1，因为我们需要再次考虑当前字符，使用 ' continue' 关键字继续迭代。
将“last”变量的值更新为“j”。
循环的所有迭代完成后返回“cnt + 1”。这里，我们需要将“cnt”添加“1”，因为我们不考虑最后一个操作。
#include <iostream>
using namespace std;
// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
int len = str1.length();
// creating an array of size 26 to store the presence of characters in string str1.
int arr[26] = {0};
// storing the presence of characters in string str1.
for (int i = 0; i < len; i++){
arr[str1[i] - 'a']++;
}
// store the last iterated index of string str1.
int last = -1;
// to store the count of operations.
int cnt = 0;
for (int i = 0; i < str2.length(); i++){
char ch = str2[i];
// if the character is not present in string str1, then return -1.
if (arr[ch - 'a'] == 0){
return -1;
}
// start iterating from the jth index of string str1 to find the character ch.
int j = last + 1;
while (j < len && str1[j] != ch){
j++;
}
// if j is equal to the length of string str1, then increment the count, set last to -1, and decrement i.
if (j >= len){
cnt++;
last = -1;
--i;
continue;
}
// set last to j.
last = j;
}
// return cnt + 1 as we haven't counted the last operation.
return cnt + 1;
}
int main(){
string str1 = "acd", str2 = "adc";
int operations = minOperations(str1, str2);
cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
return 0;
}
Minimum number of operations required to create string B from the subsequences of the string A is: 2
时间复杂度 – O(N*M)，其中 N 是 str2 的长度，M 是 str1 的长度。
空间复杂度 - O(1)，因为我们不使用任何动态空间。
在这种方法中，我们将使用映射和集合数据结构来提高上述方法的效率。解决问题的逻辑与上面的方法相同。
定义“chars_mp”以将 char -> 集{}存储为键值对。
在映射中，存储 str1 字符串中存在特定字符的索引集
定义“last”和“cnt”变量
开始遍历str2。如果包含当前字符索引的集合的大小为零，则返回 -1。
查找当前字符索引集中“last”的上限。
如果找不到上限，请将“cnt”的值增加 1，将“last”设置为 -1，将“I”的值减少 1，然后使用 continue 关键字。
更新“last”变量的值。
循环迭代完成后，返回‘cnt’变量的值
#include <iostream>
#include <map>
#include <set>
using namespace std;
// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
// Length of string str1
int len = str1.length();
// creating the map to store the set of indices for each character in str1
map<char, set<int>> chars_mp;
// Iterate over the characters of str1 and store the indices of each character in the map
for (int i = 0; i < len; i++){
chars_mp[str1[i]].insert(i);
}
// store the last visited index of str1
int last = -1;
// Stores the required count
int cnt = 1;
// Iterate over the characters of str2
for (int i = 0; i < str2.length(); i++){
char ch = str2[i];
// If the set of indices of str2[i] is empty, then return -1
if (chars_mp[ch].size() == 0){
return -1;
}
// If the set of indices of str2[i] is not empty, then find the upper bound of last in the set of indices of str2[i]
// It finds the smallest index of str2[i] which is greater than last
auto it = chars_mp[ch].upper_bound(last);
// If the upper bound is equal to the end of the set, then increment the count and update last to -1
if (it == chars_mp[ch].end()){
last = -1;
cnt++;
// Decrement I by 1 to process the current character again
--i;
continue;
}
// Update last to the current index
last = *it;
}
return cnt;
}
int main(){
string str1 = "adcb", str2 = "abdca";
int operations = minOperations(str1, str2);
cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
return 0;
}
Minimum number of operations required to create string B from the subsequences of the string A is: 3
时间复杂度 – O(N*logN)，因为我们遍历 str2 并找到循环中“最后一个”索引的上限。
空间复杂度 – O(N)，因为我们使用映射来存储字符索引。
以上是将字符串A所需附加的最小子序列以获得字符串B的详细内容。更多信息请关注PHP中文网其他相关文章！
