前缀是给定字符串中的子字符串，从第零个索引开始，长度可达字符串的大小。同样，后缀是任意长度为 1 到字符串大小的子字符串，并以最后一个索引结束。我们将得到两个字符串，并且必须以任何方式使用第二个字符串的任意数量的前缀和后缀来创建第一个字符串。如果无法从给定方法创建给定字符串，那么我们将返回 -1。

示例

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

Output:  2

Explanation

解释

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

Input 2: string str1 = “randomstring” string str2 = “anotherstring” 

Output: -1

Explanation

解释

我们无法从给定的第二个字符串的后缀或前缀中获取第一个字符串。

方法

为了解决这个问题，我们将使用动态规划的概念，即通过存储已经发生的实例来解决。

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

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

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

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

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

• 我们将尽力减少所需的子字符串数量，如果不可能，将返回-1。

示例

#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)，因为我们获取的所有后缀的复杂度都很高，但可以通过反转字符串来降低时间复杂度。此外，我们将字符串存储到哈希集中使得时间复杂度很高，并且嵌套 for 循环以进行动态编程。

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

结论

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