
在这个问题中,我们需要找到长度为 K 且正好包含 K 个元音的子串的总数。我们将看到解决问题的两种不同方法。我们可以使用一种简单的方法来检查每个长度为 K 的子串中元音的数量。此外,我们可以使用滑动窗口方法来解决该问题。
问题陈述——我们给出了一个长度为 N 的字符串 str,包含小写和大写字母字符。我们需要统计长度为 K 且正好包含 X 个元音的子串的总数。
输入– str = "TutorialsPoint", K = 3, X = 2
输出– 6
解释– 长度为 3 且恰好包含 2 个元音的子串是:'uto'、'ori'、'ria'、'ial'、'Poi' 和 'oin'。 p>
输入– str = ‘aeiou’, K = 2, X = 2
输出– 4
解释-长度为2且恰好包含2个元音的子串是:‘ae’、‘ei’、‘io’和‘ou’。
输入– str = ‘fghjsdfdffg’, K = 5, X = 1
输出– 0
解释-字符串str不包含任何元音,因此我们找不到任何包含1个元音的子字符串。
在这种方法中,我们将找到str的长度为K的每个子串。之后,我们将计算特定子串中元音的总数,如果发现它们等于 X,则可以将计数增加 1。
在 cntSubStr() 函数中,将“cnt”变量初始化为零,以存储子字符串的总数。
使用循环从第 0 个索引开始迭代到 len - K 索引,其中“len”是字符串的长度。
在循环中,使用 substr() 方法获取从第 i 个索引开始的长度为 K 的子字符串。
执行countVowel()函数来统计子字符串中元音的总数。
在 countVowel() 函数中,将“vowels”变量初始化为零,以存储元音总数。
遍历子字符串,当前字符为元音,将‘vowels’的值加1。
返回“元音”。
在 cntSubStr() 函数中,如果子字符串中的元音总数等于 X,则将“cnt”的值增加 1。
返回“cnt”的值。
#include <bits/stdc++.h>
using namespace std;
// function to count the total number of vowels in a string
int cntVowels(string alpha) {
int vows = 0;
for (int i = 0; i < alpha.length(); i++) {
if (alpha[i] == 'a' || alpha[i] == 'e' || alpha[i] == 'i' || alpha[i] == 'o' ||
alpha[i] == 'u' || alpha[i] == 'A' || alpha[i] == 'E' || alpha[i] == 'I' ||
alpha[i] == 'O' || alpha[i] == 'U')
vows++;
}
return vows;
}
int cntSubstr(string str, int K, int X) {
int cnt = 0;
// traverse the string and check for the total number of vowels in each substring of length K
for (int i = 0; i <= str.length() - K; i++) {
// get the substring of length K starting from index i
string sub = str.substr(i, K);
// check if the total number of vowels in the substring is equal to X, then increment cnt
if (cntVowels(sub) == X)
cnt++;
}
return cnt;
}
// Driver code
int main(void) {
string str = "TutorialsPoint";
int K = 3, X = 2;
cout << "The total number of substrings of length " << K << " containing " << X << " vowels is " << cntSubstr(str, K, X);
return 0;
}
The total number of substrings of length 3 containing 2 vowels is 6
时间复杂度– O(N*K),当我们遍历str时,遍历countVowel()函数中的子字符串。
空间复杂度– O(K),因为我们存储子字符串
我们将使用滑动窗口技术来解决这种方法中的问题。我们将从子字符串中删除第一个字符,并在末尾添加 1 个字符。另外,我们将跟踪当前子字符串中元音的计数,如果它等于 X,我们可以将计数增加 1。
定义 isVowel() 函数,根据特定字符是否为元音返回布尔值。
在 cntSubStr() 函数中,定义“total_vow”并初始化为零,以存储当前窗口中的总元音。
从第 0 个索引开始,求长度为 K 的子串中元音的总数,代表第一个窗口。
根据“vow”的值是否等于X,将“cnt”变量初始化为1或0。
开始从第 1 个位置遍历字符串到 len – K 索引。
如果 (i-1) 字符是元音,则将“total_vow”的值减 1。
如果第 (i - 1 + K) 个索引处的字符是元音,则将“total_vow”的值增加 1。
如果“total_vow”等于 X,则将“cnt”增加 1。
返回“cnt”的值。
#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch) {
// convert character to lowercase
ch = tolower(ch);
return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
int cntSubstr(string str, int K, int X) {
// To store total vowels
int total_vow = 0;
// Count the number of vowels in the first window
for (int p = 0; p < K; p++)
if (isVowel(str[p]))
total_vow++;
// to store the total number of substrings of length K containing X vowels
int cnt = 0;
// If the first window contains exactly X vowels, initialize cnt as 1
cnt = total_vow == X ? 1 : 0;
// traverse the string
for (int i = 1; i <= str.length() - K; i++) {
// exclude the (i - 1)th character from the window and update the total_vow
total_vow = isVowel(str[i - 1]) ? total_vow - 1 : total_vow;
// Add [i-1+K]th character to the current window and update total_vow
total_vow = isVowel(str[i - 1 + K]) ? total_vow + 1 : total_vow;
// If the current window contains exactly X vowels, increment cnt
if (total_vow == X)
cnt++;
}
return cnt;
}
int main(void) {
string str = "TutorialsPoint";
int K = 3, X = 2;
cout << "The total number of substrings of length " << K << " containing " << X << " vowels is " << cntSubstr(str, K, X);
return 0;
}
The total number of substrings of length 3 containing 2 vowels is 6
时间复杂度 - O(N),因为我们遍历字符串。
空间复杂度 - O(1),因为我们不使用任何额外的空间。
我们优化了第二种方法并降低了代码的时间复杂度。此外,我们还优化了第二种方法的空间复杂度。在这里,我们找到了恰好包含 X 个元音字母的长度为 K 的子串总数,但是程序员可以尝试找到恰好包含 K 个元音字母的任意长度的子串总数。
以上就是包含恰好X个元音字母的长度为K的子串的数量的详细内容,更多请关注php中文网其它相关文章!
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号