檢查一個字串是否可以分割成三個子字串，其中一個子字串是另外兩個子字串的子字串

在這個問題中，我們需要分割給定的字串，使得第三個子字串可以是前兩個子字串的子字串。

讓我們想想解決辦法。僅當兩個字串包含第三個字串的所有字元時，第三個字串才可以是前兩個字串的子字串。所以，我們需要在給定的字串中找到至少一個出現頻率大於3的字符，並且我們可以取該單一字符的第三個子串。

問題陳述 - 我們給了一個包含 N 個小寫字母字元的字串 str。我們需要檢查是否可以將字串拆分為三個子字串 a、b 和 c，使得子字串 c 是 a 和 b 的子字串。根據是否能找到 3 個子字串，列印「yes」或「no」。

範例

Input –  str = "tutorialsPoint"

Output – ‘Yes’

說明

在這裡，我們可以將字串拆分為「tu」、「torialsPoin」和「t」。因此，第三個字串是前兩個字串的子字串。

Input –  str = "tutorials"

Output – ‘No’

說明

我們無法根據給定條件將字串拆分為三個子字串，因為任何字元的頻率都不大於 3。

Input –  str = "hhhhhhhh"

Output – ‘Yes’

說明

根據給定條件，三個子字串可以是‘h’、‘h’和‘hhhhhh’。

方法 1

在這種方法中，我們將使用一個陣列來儲存每個字元的頻率。之後，我們將檢查頻率大於或等於3的字元。

演算法

• 步驟 1 - 定義長度等於 26 的「freq」陣列。

• 步驟 2 - 遍歷字串以計算字元的頻率。在 for 迴圈中，增加 freq[str[i] – ‘a’] 的值。這裡，str[i] – ‘a’給出0到26之間的索引。

• 第 3 步 - 現在，遍歷“freq”數組，如果任意數組索引處的值大於“3”，則傳回 true。

• 第 4 步 - 循環終止時傳回 true。

• 第 5 步 - 根據 isSUbStringPossible() 函數的回傳值列印「是」或「否」。

範例

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   // array to store the frequency
   int freq[26] = {0};
   
   // Iterate over the string
   for (int i = 0; i < len; i++){
   
      // count the frequency of each character
      freq[str[i] - 'a']++;
   }
   
   // Traverse the frequency array
   for (int i = 0; i < 26; i++){
   
      // If the frequency of any character is greater than or equal to 3, then return "Yes."
      if (freq[i] >= 3){
         return "Yes";
      }
   }
   
   // Otherwise
   return "No";
}
int main(){
   string str = "tutorialsPoint";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

輸出

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

時間複雜度 - O(N)，當我們遍歷字串時。

空間複雜度 - O(1)，因為我們使用恆定長度的陣列。

方法2

在這種方法中，我們首先將字串轉換為字元陣列。之後，我們使用 count() 方法來統計數組中特定字元的出現頻率。

演算法

• 第 1 步 - 建立一個大小為「len 1」的數組，其中「len」是字串長度。

• 第 2 步 - 使用 strcpy() 方法將字串複製到 char 陣列中。

• 第 3 步 - 使用 for 迴圈進行總共 26 次迭代。

• 步驟 4 - 在 for 迴圈中，使用 count() 方法來計算特定字元的出現次數。

count() 方法將對開始位置的參考作為第一個參數，對結束位置的參考作為第二個參數，以及一個字元作為第三個參數。

在這裡，我們需要將字元的 ASCII 值作為參數傳遞，我們使用 I ‘a’ 來取得該值。

• 第 5 步 - 如果 count() 方法傳回大於或等於 3，則傳回 true。

• 第 6 步 - 循環終止時傳回 false。

範例

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   //    converting str to char array.
   char char_array[len + 1];
   
   // copy string to char array
   strcpy(char_array, str.c_str());
   
   // make 26 iterations
   for (int i = 0; i < 26; i++){
   
      // Using count() to count the occurrence of each character in the array, and return 'yes' if any character occurs more than 2 times.
      if (count(char_array, char_array + len, i + 'a') >= 2)
         return "YES";
   }
   return "NO";
}
int main(){
   string str = "tutorials";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

輸出

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

時間複雜度 - O(N)，因為 count() 方法迭代 char 陣列來計算字元數。另外，strcpy() 方法需要 O(N) 時間。

空間複雜度 - O(N)，因為我們將字串儲存到字元陣列中。

結論

我們學習了兩種將字串拆分為三個子字串的方法，這樣一個子字串可以成為另外兩個子字串的子字串。第二種方法的程式碼更具可讀性，對初學者更友好，但時間和空間成本更高。

以上是檢查一個字串是否可以分割成三個子字串，其中一個子字串是另外兩個子字串的子字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！