构成给定字符串所需的字符串前缀和后缀的最小数量


前缀是从给定字符串的第零个索引开始,长度可以从1到字符串大小的子字符串。类似地,后缀是长度从1到字符串大小,并在最后一个索引结束的子字符串。我们将得到两个字符串,并必须通过以任何方式使用第二个字符串的任意数量的前缀和后缀来创建第一个字符串。如果无法通过给定的方法从给定的字符串创建给定字符串,我们将返回-1。

示例

Input 1: string str1 = “tutorialspoint” string str2 = “pointstutorial”
Output: 2

解释

我们可以使用前缀“points”和后缀“tutorial”,并将它们连接起来得到第一个字符串。这只需要两个子字符串,这就是我们的答案或输出。

Input 2: string str1 = “randomstring” string str2 = “anotherstring”
Output: -1

解释

没有办法从给定第二个字符串的后缀或前缀中得到第一个字符串。

方法

为了解决这个问题,我们将使用动态规划的概念,即存储已经发生的情况。

  • 首先,我们将创建一个函数,该函数将两个字符串作为参数并返回一个整数。

  • 在函数中,我们将首先获取字符串的长度,并创建一个哈希集和一个临时字符串来获取前缀。

  • 我们将遍历第二个字符串并获取所有前缀,并将它们存储在哈希集中。同样,通过从后向前遍历字符串,我们可以获取所有后缀并将它们存储在哈希集中。

  • 然后,我们将创建一个数组来存储动态规划的结果,并在数组的每个索引处存储-1。

  • 使用嵌套for循环,我们将第一个字符串分成块,并找到是否可以从哈希映射中连接所有块。

  • 我们将尝试减少所需的子字符串数量,如果不可能,则返回-1。

示例

Open Compiler
#include <bits/stdc++.h> using namespace std; // function to find the required number of substrings int count(string str1, string str2){ unordered_set<string> st; // set to store the strings from the prefix and suffix string temp = "";// string to store the prefixes and suffixes int len1 = str1.size(); // size of the first string int len2 = str2.size(); // getting size of the second // getting prefixes of string second for (int i = 0; i < len2; i++){ temp += str2[i]; // adding the characters to temporary string st.insert(temp); // insert current string to set } // getting all the sufixes for (int i = len2-1; i >= 0; i--){ temp = str2.substr(i); // getting suffixes st.insert(temp); // adding suffixes to the set } // Initialize memo array to store the answer int memo[len1+1]; memset(memo, -1, sizeof(memo)); // initializing array memo[0] = 0; // applying the concepts of dp // traversing over the main string and will try to // partition string into chunks for (int i = 0; i < len1; i++){ for (int j = 1; j <= len1 - i; j++){ // check if the set contain current substring if (st.find(str1.substr(i, j)) != st.end()){ if (memo[i] == -1){ continue; } if (memo[i + j] == -1){ memo[i + j] = memo[i] + 1; } else { memo[i + j] = min(memo[i + j], memo[i] + 1); } } } } // Return the answer return memo[len1]; } int main(){ string str1 = "tutorialpoints"; string str2 = "pointstutorial"; // calling function to find the minimum number of substrings required cout <<"The minimum count of prefixes and suffixes of a string required to form given string is "<<count(str1, str2)<<endl; return 0; }

输出

The minimum count of prefixes and suffixes of a string required to form given string is 2

时间和空间复杂度

上述代码的时间复杂度为O(N^2),因为我们正在获取所有后缀的复杂度为O(N^2),但这可以通过反转字符串来减少。此外,我们将字符串存储到哈希集中,使得时间复杂度为O(N^2),而动态规划的嵌套for循环也为O(N^2)。

上述代码的空间复杂度为O(N^2),因为我们将所有后缀和前缀存储在哈希映射中。

结论

在本教程中,我们实现了一个代码来查找作为给定字符串的后缀和前缀的最小子字符串数量,以创建另一个给定字符串,如果不可能,我们打印-1。我们使用了动态规划的概念,将元素存储在哈希集中,然后使用嵌套循环,时间和空间复杂度为O(N^2)。

更新于:2023年7月26日

285 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告