数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究包含恰好X个元音的长度为K的子字符串计数
在这个问题中，我们需要找到包含恰好K个元音的长度为K的子字符串的总数。我们将看到解决这个问题的两种不同方法。我们可以使用一种朴素的方法来检查长度为K的每个子字符串中元音的数量。此外，我们还可以使用滑动窗口方法来解决这个问题。
问题陈述– 我们给定一个长度为N的字符串str，其中包含小写和大写字母字符。我们需要计算包含恰好X个元音的长度为K的子字符串的总数。
示例
输入– str = "TutorialsPoint", K = 3, X = 2
输出– 6
说明– 包含恰好2个元音的长度为3的子字符串为：‘uto’，‘ori’，‘ria’，‘ial’，‘Poi’和‘oin’。
输入– str = ‘aeiou’, K = 2, X = 2
输出– 4
说明– 包含恰好2个元音的长度为2的子字符串为：‘ae’，‘ei’，‘io’和‘ou’。
输入– str = ‘fghjsdfdffg’, K = 5, X = 1
输出– 0
说明– 字符串str不包含任何元音，因此我们找不到包含1个元音的子字符串。
方法1
在这种方法中，我们将找到str长度为K的每个子字符串。之后，我们将计算特定子字符串中元音的总数，如果我们发现它们等于X，我们可以将计数增加1。
算法
在cntSubStr()函数中，用零初始化‘cnt’变量以存储子字符串的总数。
使用循环进行迭代，从第0个索引开始到len – K索引，其中‘len’是字符串的长度。
在循环中，使用substr()方法获取从第i个索引开始的长度为K的子字符串。
执行countVowel()函数以计算子字符串中的元音总数。
在countVowel()函数中，用零初始化‘vowels’变量以存储元音的总数。
遍历子字符串，如果当前字符是元音，则将‘vowels’的值增加1。
返回‘vowels’。
在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)，因为我们在countVowel()函数中遍历str，遍历子字符串。
空间复杂度– O(K)，因为我们存储子字符串
方法2
在这种方法中，我们将使用滑动窗口技术来解决这个问题。我们将从子字符串中删除第一个字符，并在末尾添加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个元音的任意长度的子字符串的总数。
90 次浏览
