C++ 将给定的字符串最小分割以获得另一个字符串

在这个问题中，我们需要通过切割另一个字符串来构造一个字符串。我们可以使用最长公共子串来解决这个问题。我们可以找到两个字符串之间的最长公共子串，将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

说明 - 我们|欢迎

方法1

在这个方法中，我们将找到给定字符串之间的最长公共子串，切割字符串并从两个字符串中删除子串。此外，我们会在每次迭代中更新两个字符串，直到str2字符串变为空。

此外，我们还需要注意切割起始部分和结束部分，因为在这种情况下我们只需要1个切片。此外，如果字符已经在子串中计数过了，我们将字符str1更新为“0”。

算法

步骤1 - 如果str1的大小小于str2，则返回-1，因为无法构建str2。如果两个字符串相同，则返回0。

步骤2 - 初始化’answer’为0，用于存储str1的总切片数。

步骤3 - 使用while循环进行迭代，直到str2的大小大于零。

步骤4 - 执行longCommonSubStr()函数以获取str1和str2中的最长公共子串。

步骤4.1 - 在longCommonSubStr()函数中，用0初始化’maxLen’变量以存储最大长度，用0初始化’endingStr1’和’endingStr2’以存储子串在str1和str2中的结束索引。此外，使用动态规划方法来找到最长公共子串并将其存储在’mat’中的前一个结果，并将’currentRow’初始化为0。

步骤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 - 否则，将0赋值给mat[currentRow][q] = 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步 - 如果我们需要从中间切割字符串，在str1中，如果子字符串的前一个字符和后一个字符都不等于’0’，则相应地增加’answer’值。

第8步 - 使用substr()方法从str2中删除公共子字符串。

第9步 - 通过执行replaceSubStr()函数，将所有子字符串字符替换为’0’，来更新str1字符串。

第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(NMM)，其中 O(N*M) 用于找到最长公共子串，O(M) 用于缩小字符串 str2。

空间复杂度 – O(N)，其中 O(N) 用于存储动态规划结果。