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

前缀是从给定字符串的零索引开始并可以到达字符串长度的任意长度的子字符串。同样，后缀是任意长度为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。

• 使用嵌套的循环，我们将把第一个字符串分为块，并找出是否可以从哈希表连接所有的块。

• 我们将尽量减少所需的子字符串数量，如果不可能，则返回-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)的嵌套循环。