Die Anzahl der Teilzeichenfolgen der Länge K, die genau X Vokale enthalten

In diesem Problem müssen wir die Gesamtzahl der Teilzeichenfolgen der Länge K ermitteln, die genau K Vokale enthalten. Wir werden zwei verschiedene Möglichkeiten zur Lösung des Problems sehen. Mit einer einfachen Methode können wir die Anzahl der Vokale in jedem Teilstring der Länge K überprüfen. Darüber hinaus können wir dieses Problem mit einem Schiebefenster-Ansatz lösen.

Problemstellung – Wir erhalten eine Zeichenfolge str der Länge N, die Klein- und Großbuchstaben enthält. Wir müssen die Gesamtzahl der Teilzeichenfolgen der Länge K zählen, die genau X Vokale enthalten.

Beispiel

Eingabe– str = „TutorialsPoint“, K = 3, X = 2

Ausgabe– 6

Erklärung– Teilzeichenfolgen der Länge 3, die genau 2 Vokale enthalten, sind: „uto“, „ori“, „ria“, „ial“, „Poi“ und „oin“. p>

Eingabe– str = ‚aeiou‘, K = 2, X = 2

Ausgabe– 4

Erklärung- Teilzeichenfolgen der Länge 2, die genau 2 Vokale enthalten, sind: „ae“, „ei“, „io“ und „ou“.

Eingabe– str = ‚fghjsdfdffg‘, K = 5, X = 1

Ausgabe– 0

Erklärung- Die Zeichenfolge str enthält keine Vokale, daher können wir keine Teilzeichenfolge finden, die 1 Vokal enthält.

Methode 1

Mit dieser Methode finden wir jeden Teilstring der Länge K von str. Danach zählen wir die Gesamtzahl der Vokale in einer bestimmten Teilzeichenfolge und wenn wir feststellen, dass sie gleich X sind, können wir die Anzahl um 1 erhöhen.

Algorithmus

• Initialisieren Sie in der Funktion cntSubStr() die Variable „cnt“ auf Null, um die Gesamtzahl der Teilzeichenfolgen zu speichern.

• Verwenden Sie eine Schleife, um vom 0. Index zu den len-K-Indizes zu iterieren, wobei „len“ die Länge der Zeichenfolge ist.

• Verwenden Sie in der Schleife die Methode substr(), um den Teilstring der Länge K ab dem i-ten Index abzurufen.

• Führen Sie die Funktion countVowel() aus, um die Gesamtzahl der Vokale in der Teilzeichenfolge zu zählen.

• Initialisieren Sie in der Funktion countVowel() die Variable „vowels“ auf Null, um die Gesamtzahl der Vokale zu speichern.

• Durchlaufen Sie die Teilzeichenfolge, das aktuelle Zeichen ist ein Vokal, und addieren Sie 1 zum Wert von „Vokale“.

• Zurück zu „Vokal“.

• Wenn in der Funktion cntSubStr() die Gesamtzahl der Vokale in der Teilzeichenfolge gleich X ist, erhöhen Sie den Wert von „cnt“ um 1.

• Gibt den Wert von „cnt“ zurück.

Beispiel

#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;
}

Ausgabe

The total number of substrings of length 3 containing 2 vowels is 6

Zeitkomplexität– O(N*K), wenn wir über str iterieren, iterieren wir über die Teilzeichenfolgen in der Funktion countVowel().

Raumkomplexität – O(K), da wir Teilzeichenfolgen speichern

Methode 2

Wir werden die Schiebefenstertechnik verwenden, um die Probleme in diesem Ansatz zu lösen. Wir entfernen das erste Zeichen aus der Teilzeichenfolge und fügen am Ende 1 Zeichen hinzu. Darüber hinaus verfolgen wir die Anzahl der Vokale in der aktuellen Teilzeichenfolge. Wenn diese gleich X ist, können wir die Anzahl um 1 erhöhen.

Algorithmus

• Definieren Sie die Funktion isVowel(), um einen booleschen Wert zurückzugeben, basierend darauf, ob ein bestimmtes Zeichen ein Vokal ist.

• In der Funktion cntSubStr() definieren Sie „total_vow“ und initialisieren es auf Null, um die Gesamtzahl der Vokale im aktuellen Fenster zu speichern.

• Ermitteln Sie ausgehend vom 0. Index die Gesamtzahl der Vokale in der Teilzeichenfolge der Länge K, die das erste Fenster darstellt.

• Initialisieren Sie die Variable „cnt“ auf 1 oder 0, je nachdem, ob der Wert von „vow“ gleich X ist.

• Beginnen Sie mit dem Durchlaufen der Zeichenfolge von Position 1 bis zum Index len – K.

• Wenn das (i-1)-Zeichen ein Vokal ist, dekrementieren Sie den Wert von „total_vow“ um 1.

• Wenn das Zeichen am (i - 1 + K)-ten Index ein Vokal ist, erhöhen Sie den Wert von „total_vow“ um 1.

• Wenn „total_vow“ gleich X ist, erhöhen Sie „cnt“ um 1.

• Gibt den Wert von „cnt“ zurück.

Beispiel

#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;
}

Ausgabe

The total number of substrings of length 3 containing 2 vowels is 6

Zeitkomplexität – O(N), da wir über die Zeichenfolge iterieren.

Raumkomplexität – O(1), da wir keinen zusätzlichen Raum verbrauchen.

Wir haben die zweite Methode optimiert und die zeitliche Komplexität des Codes reduziert. Darüber hinaus optimieren wir auch die räumliche Komplexität der zweiten Methode. Hier finden wir die Gesamtzahl der Teilzeichenfolgen der Länge K, die genau X Vokale enthalten, aber der Programmierer könnte versuchen, die Gesamtzahl der Teilzeichenfolgen beliebiger Länge zu ermitteln, die genau K Vokale enthalten.

Das obige ist der detaillierte Inhalt vonDie Anzahl der Teilzeichenfolgen der Länge K, die genau X Vokale enthalten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!