数据结构
网络
关系数据库管理系统 (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 次浏览
