数据结构
网络
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 次查看
