包含恰好X個元音字母的長度為K的子串的數量

在這個問題中，我們需要找到長度為 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 <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)，因為我們儲存子字串

方法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 個元音字母的任意長度的子字串總數。

以上是包含恰好X個元音字母的長度為K的子串的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！