資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學檢查一個字串是否可以拆分成三個子字串，其中一個子字串是另外兩個子字串的子字串
在這個問題中，我們需要以這樣的方式分割給定的字串：第三個子字串可以是前兩個子字串的子字串。
讓我們思考一下解決方案。只有當前兩個字串包含第三個字串的所有字元時，第三個字串才能成為前兩個字串的子字串。因此，我們需要找到給定字串中至少一個頻率大於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'。
方法一
在這種方法中，我們將使用一個數組來儲存每個字元的頻率。之後，我們將檢查頻率大於或等於3的字元。
演算法
步驟1 - 定義長度為26的'freq'陣列。
步驟2 - 遍歷字串以計算字元的頻率。在for迴圈中，遞增freq[str[i] - 'a']的值。這裡，str[i] - 'a'給出0到26之間的索引。
步驟3 - 現在，遍歷'freq'陣列，如果任何陣列索引的值大於'3'，則返回true。
步驟4 - 迴圈終止時返回true。
步驟5 - 根據isSUbStringPossible()函式返回的值列印'yes'或'no'。
示例
#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)，因為我們使用了常數長度的陣列。
方法二
在這種方法中，我們首先將字串轉換成字元陣列。之後，我們使用count()方法計算陣列中特定字元的頻率。
演算法
步驟1 - 建立一個大小為'len + 1'的陣列，其中'len'是字串長度。
步驟2 - 使用strcpy()方法將字串複製到char陣列。
步驟3 - 使用for迴圈進行總共26次迭代。
步驟4 - 在for迴圈中，使用count()方法計算特定字元的出現次數。
步驟5 - 如果count()方法返回大於或等於3的值，則返回true。
步驟6 - 迴圈終止時返回false。
count()方法將起始位置的引用作為第一個引數，結束位置的引用作為第二個引數，以及字元作為第三個引數。
在這裡，我們需要傳遞字元的ASCII值作為引數，我們可以使用I + 'a'得到。
示例
#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)，因為我們將字串儲存在字元陣列中。
結論
我們學習了兩種將字串分割成三個子字串的方法，使得其中一個子字串可以是另外兩個子字串的子字串。第二種方法的程式碼更易讀，也更適合初學者，但是它在時間和空間方面開銷更大。
99 次瀏覽
