为了得到字符串 B，需要从字符串 A 中追加的最少子序列
在这道题中，我们需要使用字符串 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"。
方法 1
在此方法中，我们将迭代 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;
// 函数用于计算从字符串 str1 的子序列中获取字符串 str2 所需的最少操作次数。
int minOperations(string str1, string str2){
int len = str1.length();
// 创建一个大小为 26 的数组，用于存储字符串 str1 中字符的存在情况。
int arr[26] = {0};
// 存储字符串 str1 中字符的存在情况。
for (int i = 0; i < len; i++){
arr[str1[i] - 'a']++;
}
// 存储字符串 str1 的最后一个迭代索引。
int last = -1;
// 存储操作次数。
int cnt = 0;
for (int i = 0; i < str2.length(); i++){
char ch = str2[i];
// 如果该字符不存在于字符串 str1 中，则返回 -1。
if (arr[ch - 'a'] == 0){
return -1;
}
// 从字符串 str1 的第 j 个索引开始迭代以找到字符 ch。
int j = last + 1;
while (j < len && str1[j] != ch){
j++;
}
// 如果 j 等于字符串 str1 的长度，则增加计数，将 last 设置为 -1，并减少 i。
if (j >= len){
cnt++;
last = -1;
--i;
continue;
}
// 将最后设置为 j。
last = j;
}
// 返回 cnt + 1，因为我们还没有计算最后一个操作。
return cnt + 1;
}
int main(){
string str1 = "acd", str2 = "adc";
int operations = minOperations(str1, str2);
cout << "从字符串 A 的子序列创建字符串 B 所需的最少操作数为: " << operations << "\n";
return 0;
}
输出
从字符串 A 的子序列创建字符串 B 所需的最少操作数为: 2
时间复杂度 – O(N*M)，其中 N 是 str2 的长度，M 是 str1 的长度。
空间复杂度 – O(1)，因为我们不使用任何动态空间。
方法 2
在此方法中，我们将使用 map 和 set 数据结构来提高上述方法的效率。解决问题的逻辑与上述方法相同。
算法
定义 'chars_mp' 以将 char -> set{} 存储为键值对。
在 map 中，存储 str1 字符串中特定字符所在的索引集合。
定义 'last' 和 'cnt' 变量
开始遍历 str2。如果包含当前字符索引的集合大小为零，则返回 -1。
在当前字符索引集合中查找"last"的上限。
如果未找到上限，则将"cnt"的值增加 1，将"last"设置为 -1，将"I"的值减少 1，然后使用 continue 关键字。
更新"last"变量的值。
循环迭代完成后，返回"cnt"变量的值
示例
#include <iostream>
#include <map>
#include <set>
using namespace std;
// 函数用于计算从字符串 str1 的子序列中获取字符串 str2 所需的最少操作次数。
int minOperations(string str1, string str2){
// 字符串 str1 的长度
int len = str1.length();
// 创建映射来存储 str1 中每个字符的索引集合
map<char, set<int>> chars_mp;
// 遍历 str1 中的字符，并将每个字符的索引存储在 map 中
for (int i = 0; i < len; i++){
chars_mp[str1[i]].insert(i);
}
// 存储 str1 中最后访问的索引
int last = -1;
// 存储所需的计数
int cnt = 1;
// 遍历 str2 中的字符
for (int i = 0; i < str2.length(); i++){
char ch = str2[i];
// 如果 str2[i] 的索引集合为空，则返回 -1
if (chars_mp[ch].size() == 0){
return -1;
}
// 如果 str2[i] 的索引集合不为空，则在 str2[i] 的索引集合中找到 last 的上界
// 找到 str2[i] 中大于 last 的最小索引
auto it = chars_mp[ch].upper_bound(last);
// 如果上界等于集合的末尾，则增加计数并将 last 更新为 -1
if (it == chars_mp[ch].end()){
last = -1;
cnt++;
// 将 I 减 1 以再次处理当前字符
--i;
continue;
}
//更新最后到当前索引
last = *it;
}
return cnt;
}
int main(){
string str1 = "adcb", str2 = "abdca";
int operations = minOperations(str1, str2);
cout << "从字符串 A 的子序列创建字符串 B 所需的最少操作数为: " << operations << "\n";
return 0;
}
输出
从字符串 A 的子序列创建字符串 B 所需的最少操作数为: 3
时间复杂度 – O(N*logN)，因为我们遍历 str2 并在循环中找到"最后一个"索引的上界。
空间复杂度 – O(N)，因为我们使用 map 来存储字符索引。
