C++ 需要附加到字符串A以得到字符串B的最小子序列

在这个问题中，我们需要利用字符串A的子序列来构造字符串B。为了解决这个问题，我们可以找到字符串A的子序列，使其覆盖字符串B的最大长度的子串。在这里，我们将学习解决这个问题的两种不同方法。

问题陈述 -我们已经给出了两个不同长度的字符串，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。

• 将变量’j’初始化为’last + 1’。

• 使用while循环进行迭代，直到’j’的值小于len且str1[j]不等于字符。

• 如果’j’的值大于’len’，我们遍历了’str1’。增加变量’cnt’的值，将’last’初始化为-1，因为我们需要再次遍历’str1’，将’I’的值减1，因为我们需要重新考虑当前字符，使用’continue’关键字继续迭代。

• 通过’j’更新变量’last’的值。

• 在循环的所有迭代完成后，返回’cnt + 1’。在这里，我们需要将1添加到’cnt’，因为我们不考虑最后一次操作。

示例

#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)，因为我们不使用任何动态空间。

方法2

在这种方法中，我们将使用映射和集合数据结构来使上述方法更加高效。解决问题的逻辑与上述方法相同。

步骤

• 定义’chars_mp’以存储char -> set {}作为键值对。

• 在映射中，存储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并在循环中找到’last’索引的上限。

空间复杂度 - O(N)，因为我们使用map来存储字符的索引。