獲取字串 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。

• 將“j”變數初始化為“last + 1”的值。

• 使用 while 迴圈進行迭代，直到“j”的值小於 len，並且 str1[j] 不等於字元

• 如果“j”的值大於“len”，我們將遍歷“str1”。增加“cnt”變數的值，將“last”初始化為 -1（因為我們需要再次遍歷“str1”），將“I”的值減 1（因為我們需要再次考慮當前字元），使用“continue”關鍵字繼續迭代。

• 將“last”變數的值更新為“j”。

• 一旦迴圈的所有迭代完成，返回“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

在這種方法中，我們將使用 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;

// 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 來儲存字元的索引。