資料結構
網路
關係資料庫管理系統 (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 次瀏覽
