資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學最小化給定字串中的分割槽以獲取另一個字串
在這個問題中，我們需要透過切片另一個字串來構造一個字串。我們可以使用最長公共子串來解決這個問題。我們可以在兩個字串之間找到最長公共子串，將 str1 切分成 1 或 2 部分，並從 str2 中刪除子串。再次，我們在更新的字串中找到最長公共子串並繼續執行，直到 str2 變成空。透過這種方式，我們可以解決問題。
問題陳述 – 我們給定了 str1 和 str2 兩個長度不同的字串。我們需要透過切片和連線 str1 的部分來構造字串 str2。我們需要找到使用 str1 獲取 str2 字串所需的最小切片次數。如果無法構造 str2 字串，則列印“-1”。
示例
輸入
str1 = "tutorialspoint"; str2 = "intpotu";
輸出
3
解釋 – 如圖所示，我們需要將 str1 切分成 4 部分，共 3 次。
Tu | torials | po | int
輸入
str1 = "tutorialspoint"; str2 = "intpotu";
輸出
-1
解釋 – 由於我們無法從 str1 構造 str2。所以，它列印“-1”。
輸入
str1 = "Welcome"; str2 = "meWe";
輸出
2
解釋 – We | lco | me
方法 1
在這種方法中，我們將找到給定字串之間的最長公共子串，切分字串，並從兩個字串中刪除子串。此外，我們將在每次迭代中更新這兩個字串，並進行迭代，直到 str2 字串變為空。
此外，我們需要關注切分起始和結束部分，因為在這種情況下我們只需要 1 次切分。此外，如果字元已在子串中計算，我們將 str1 的字元更新為“0”。
演算法
步驟 1 – 如果 str1 的大小小於 str2，則返回 -1，因為無法從 str1 構造 str2。如果兩個字串相同，則返回 0。
步驟 2 – 將“answer”初始化為 0 以儲存 str1 的總切片次數。
步驟 3 – 使用 while 迴圈進行迭代，直到 str2 的大小大於零。
步驟 4 – 執行 longCommonSubStr() 函式以獲取 str1 和 str2 中的最長公共子串。
步驟 4.1 – 在 longCommonSubStr() 函式中，將“maxLen”變數初始化為 0 以儲存最大長度，“endingStr1”和“endingStr2”初始化為 0 以儲存 str1 和 str2 中子串的結束索引。另外，初始化“mat”以儲存以前的結果，因為我們使用動態規劃方法來查詢最長公共子串，並用 0 初始化“currentRow”。
步驟 4.2 – 開始填充二維矩陣。
步驟 4.3 – 如果 p 和 q 為 0，則在 mat[currentRow][q] 中儲存零。
步驟 4.4 – 如果 str1 中索引 (p-1) 處的字元和 str2 中索引 (q – 1) 處的字元相同，則透過新增到先前的對角線條目來更新 mat[currentRow][q] 的值。
步驟 4.5 – 如果更新後的值大於 maxLen 變數的值，則更新“maxLen”、“endingStr1”和“endingStr2”變數的值。
步驟 4.6 – 否則，將 mat[currentRow][q] = 0 分配為 0，因為我們需要開始一個新的子串。
步驟 4.7 – 當巢狀迴圈的迭代完成時，更新“currentRow”變數的值。
步驟 4.8 – 建立“temp”陣列以儲存最長公共子串長度，以及 str1 和 str2 中的結束索引。最後，返回“temp”陣列。
步驟 5 – 在 getMinSlices() 函式中，如果最長公共子串的長度為 0，則返回 -1。
步驟 6 - 如果子串的起始索引為 0，則如果 str1 中子串最近的下一個字元不為“0”，則將“answer”值加 1。如果結束索引等於“len – 1”，則如果子串之前的字元不為“0”，則將“answer”值加 1。如果為“0”，則該部分已切分，因此我們不需要增加“answer”的值。
步驟 7 – 如果我們需要從中間切分字串，則如果子串之前和之後的字元不等於“0”，則相應地增加“answer”的值。
步驟 8 – 使用 substr() 方法從 str2 中刪除公共子串。
步驟 9 – 透過執行 replaceSubStr() 函式更新 str1 字串，該函式將所有子串字元替換為“0”。
步驟 9.1 – 在 replaceSubStr() 函式中，使用 substr() 方法從字串中獲取初始子串。之後，建立一個包含與子串長度相等的總零的中字串，並獲取結束子串。
步驟 9.2 – 連線初始、中間和結束字串後返回字串。
步驟 10 – 返回“answer”值。
示例
#include <bits/stdc++.h>
using namespace std;
int *longCommonSubStr(string str1, string str2) {
// String sizes
int len1 = str1.size();
int len2 = str2.size();
// To store the maximum length of the common substring.
int maxLen = 0;
// For storing the ending index of the substring.
int endingStr1 = 0;
int endingStr2 = 0;
// 2D array to store max len of consecutive rows
int mat[2][len1 + 1];
// Pointer to the row
int currentRow = 0;
// Finding the longest common substring
for (int p = 0; p <= len1; p++) {
for (int q = 0; q <= len2; q++) {
if (p == 0 || q == 0) {
mat[currentRow][q] = 0;
} else if (str1[p - 1] == str2[q - 1]) {
mat[currentRow][q] = mat[1 - currentRow][q - 1] + 1;
// If we get longer substring, update values.
if (mat[currentRow][q] > maxLen) {
maxLen = mat[currentRow][q];
endingStr1 = p - 1;
endingStr2 = q - 1;
}
} else {
mat[currentRow][q] = 0;
}
}
// Change the current row
currentRow = 1 - currentRow;
}
// Storing the starting index of longest common substring
int *temp = new int[3];
temp[0] = (endingStr1 - maxLen + 1);
temp[1] = (endingStr2 - maxLen + 1);
temp[2] = maxLen;
return temp;
}
string replaceSubStr(string str1, int ind, int sub_len) {
// Get initial string
string start = str1.substr(0, ind);
string mid = "";
// Create string with all 0's
for (int p = 0; p < sub_len; p++) {
mid += "0";
}
// Get remaining string
string end = str1.substr(ind + sub_len);
// Return final string
return (start + mid + end);
}
int getMinSlices(string str1, string str2) {
// Return -1 if length of str2 is greater
if (str1.size() < str2.size())
return -1;
// Handle the case when both strings are equal.
if (str1 == str2)
return 0;
int answer = 0, len1 = (str1.size() - 1);
// Find longest common substring of str1 and str2, until str2 is empty.
while (str2.size() > 0) {
int *lcs = longCommonSubStr(str1, str2);
// If the length of the substring is 0, return -1
if (lcs[2] == 0)
return -1;
// Handling the case when starting point is 0, or the ending point is len1
if ((lcs[0] + lcs[2] - 1 == len1) || lcs[0] == 0) {
// If the startind index is 0, and the last character is not '0', we need to slice. Otherwise, it's already sliced.
if (lcs[0] == 0) {
if (str1[lcs[0] + lcs[2]] != '0')
answer++;
} else {
// If the ending index is len1, the previous character of the substring's first character is '0', last part of the string is already sliced.
if (str1[lcs[0] - 1] != '0')
answer++;
}
}
// When the substring is between the last and ending character
else {
// Increment answer value if strings are not sliced already.
if (str1[lcs[0] + lcs[2]] != '0') {
answer++;
}
if (str1[lcs[0] - 1] != '0') {
answer++;
}
}
// Remove lcs from str2.
str2 = str2.substr(0, lcs[1]) + str2.substr(lcs[1] + lcs[2]);
// Pleace '0' in str1 at the place of lcs
str1 = replaceSubStr(str1, lcs[0], lcs[2]);
}
// final output
return answer;
}
int main() {
string str1 = "tutorialspoint";
string str2 = "intpotu";
cout << "The minimum slices of string str1 is required to construct a string str2 is " << getMinSlices(str1, str2) << endl;
}
輸出
The minimum slices of string str1 is required to construct a string str2 is 3
時間複雜度 – O(N*M*M)，因為 O(N*M) 用於查詢最長公共子串，O(M) 用於減少 str2。
空間複雜度 – O(N)，其中 O(N) 用於儲存動態規劃結果。
85 次檢視
