形成給定字串所需的最小前綴和後綴的數量

前綴是給定字串中的子字串，從第零個索引開始，長度可達字串的大小。同樣，後綴是任意長度為 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)的嵌套循環。

以上是形成給定字串所需的最小前綴和後綴的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！