极客笔记C++ 检查一个字符串是否可以分为三个子串，其中一个是另外两个子串的子串
在这个问题中，我们需要以这样的方式分割给定的字符串，使得第三个子串可以成为前两个子串的子串。
让我们考虑解决方案。只有当前两个子串包含第三个子串的所有字符时，第三个子串才能成为前两个子串的子串。因此，我们需要在给定的字符串中找到至少一个字符的频率大于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() 函数返回的值打印 ‘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)，因为我们使用了长度恒定的数组。
方法2
在这种方法中，我们首先将字符串转换为字符数组。然后，我们使用count()方法来计算数组中某个字符的频率。
步骤
- 步骤1 - 创建一个大小为’len + 1’的数组，其中’len’是字符串的长度。
-
步骤2 - 使用strcpy()方法将字符串复制到字符数组中。
-
步骤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()方法会迭代字符数组来计算字符次数。同时，strcpy()方法需要O(N)的时间。
空间复杂度 – O(N)，因为我们将字符串存储到字符数组中。
结论
我们学习了两种方法来将字符串分割成三个子字符串，使其中一个子字符串可以是其他两个子字符串的子串。第二种方法的代码更易读，适合初学者，但是它的时间和空间开销更大。