在这个问题中，我们需要找到长度为 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个元音的子字符串。
方法 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 using namespace std;// function to count the total number of vowels in a stringint 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 codeint 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)，因为我们存储子字符串
方法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 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的子串的数量的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444196.html
微信扫一扫 
支付宝扫一扫 
