The minimum number of prefixes and suffixes required to form a given string

The prefix is ​​a substring within the given string, starting at the zeroth index and up to the size of the string. Likewise, the suffix is ​​any substring of length 1 to the size of the string, ending at the last index. We will be given two strings and the first string must be created in any way using any number of prefixes and suffixes from the second string. If the given string cannot be created from the given method, then we will return -1.

Example

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

Output:  2

The Chinese translation of

Explanation

is:

Explanation

We can use the prefix "points" and the suffix "tutorial", and by concatenating them, we can get the first string. This only requires two substrings and this is our answer or output.

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

Output: -1

The Chinese translation of

Explanation

is:

Explanation

We cannot get the first string from the given suffix or prefix of the second string.

method

To solve this problem, we will use the concept of dynamic programming, which is solved by storing instances that have already occurred.

• First, we will create a function that will take two strings as parameters and return an integer.

• In this function, first we will get the length of the string and create a hash set and a temporary string to get the prefix.

• We will iterate through the second string and get all the prefixes and store them in a hash set. Likewise, by traversing the string from back to front, we can get all the suffixes and store them in a hash set.

• We will then create an array to store the results of dynamic programming and store -1 at each index position of the array.

• Using nested for loops, we split the first string into chunks and find if we can concatenate all the chunks in the hash map.

• We will try our best to reduce the number of substrings required, if this is not possible, -1 will be returned.

Example

#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;
}

Output

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

Time and space complexity

The time complexity of the above code is O(N^2) because the complexity of all the suffixes we obtain is high, but the time complexity can be reduced by reversing the string. Additionally, we store strings into hash sets making the time complexity high, and nest for loops for dynamic programming.

The space complexity of the above code is O(N^2) because we store all suffixes and prefixes in a hash map.

in conclusion

In this tutorial, we implemented a code to find the minimum number of substrings in the suffix and prefix of a given string to create another given string, if it is not possible, we print -1. We used the concept of dynamic programming by storing the elements in a hash set and then using nested loops with time and space complexity of O(N^2).

The above is the detailed content of The minimum number of prefixes and suffixes required to form a given string. For more information, please follow other related articles on the PHP Chinese website!