在這個問題中，我們需要使用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中文網其他相關文章！
