Der längste Teilstring mit K verschiedenen Vokalen

In diesem Artikel werden wir das Problem untersuchen, die längste Teilzeichenfolge zu finden, die K verschiedene Vokale in einer bestimmten Zeichenfolge enthält. Dieses Problem kann in C++ mit verschiedenen Algorithmen gelöst werden. Dieses Problem tritt häufig im Bereich der Informatik auf, insbesondere bei Textverarbeitungs- und Verarbeitungsaufgaben natürlicher Sprache. Es untersucht die Fähigkeit einer Person, Zeichenfolgen zu manipulieren und Grenzfälle zu verarbeiten.

Grammatik

Im C++-Feld repräsentiert die Klasse std::string den String-Datentyp. Diese vielseitige Einheit kann zum Speichern und Bearbeiten von Zeichenfolgen verwendet werden.

Die Vorlagenklasse std::vector verkörpert die Eigenschaften dynamischer Arrays und ermöglicht die Anpassung der Array-Größe und die Ausführung einer Reihe von Operationen an den gekapselten Elementen.

Als Klassenvorlage kapselt std::unordered_map eine ungeordnete Zuordnungsstruktur. Es ermöglicht das Speichern eines einzelnen Schlüssel-Wert-Paares, bei dem die Schlüssel nicht übereinstimmen, und die Werte können mit diesen verschiedenen Schlüsseln abgerufen werden.

Die Funktionsvorlage std::max gibt das Maximum von zwei Werten zurück. Dieser vielseitige Mechanismus erleichtert den Vergleich aller Datentypen, sofern der >-Operator korrekt definiert ist.

std::string
std::vector
std::unordered_map
std::max

Algorithmus

• Starten

• Initialisieren Sie die Variable, um den längsten Teilstring und seine Länge zu speichern.

• Durchlaufen Sie die Zeichenfolge, um Teilzeichenfolgen mit K verschiedenen Vokalen zu finden.

• Vergleichen Sie die Länge der Teilzeichenfolgen und aktualisieren Sie die längste Teilzeichenfolge und ihre Länge entsprechend.

• Wiederholen Sie die Schritte 2 und 3, bis alle Teilzeichenfolgen ausgewertet wurden.

• Gibt den längsten Teilstring zurück.

• Ende

Methode

• Methode 1 – Brute Force

• Methode 2 − Schiebefenster

Methode 1: Brute-Force-Cracking

Diese Implementierung verkörpert eine Brute-Force-Methode zum Ermitteln des längsten Teilstrings eines Strings mit genau k eindeutigen Vokalen. Der Code beginnt mit der Definition zweier Hilfsfunktionen: is_vowel und has_k_distinct_vowels.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Die Funktion

is_vowel empfängt ein einzelnes Zeichen als Eingabe und gibt einen wahren Wert zurück, wenn das Zeichen ein Vokal ist (z. B. „a“, „e“, „i“, „o“ oder „u“), und einen falschen Wert ansonsten. Diese Funktion wurde später verwendet, um festzustellen, ob ein Zeichen ein Vokal war.

Die Funktion

has_k_distinct_vowels akzeptiert eine Zeichenfolge und eine ganze Zahl k als Eingabe und gibt einen wahren Wert zurück, wenn die Zeichenfolge genau k eindeutige Vokale enthält, andernfalls gibt sie einen falschen Wert zurück. Diese Funktion verwendet unordered_set, um die Vokale in einer Zeichenfolge aufzuzeichnen und die Anzahl der eindeutigen Vokale in der Zeichenfolge zu zählen.

Die Hauptfunktion longest_substring_bruteforce empfängt einen String und eine ganze Zahl k als Eingabe und gibt den längsten Teilstring im String zurück, der genau k eindeutige Vokale enthält.

Dies wird erreicht, indem zwei verschachtelte for-Schleifen verwendet werden, um alle möglichen Teilzeichenfolgen der Zeichenfolge zu durchlaufen. Für jede Teilzeichenfolge wird die Funktion has_k_distinct_vowels aufgerufen, um zu überprüfen, ob die Teilzeichenfolge genau k eindeutige Vokale enthält.

Wenn der aktuelle Teilstring k eindeutige Vokale hat und breiter als der aktuell längste Teilstring ist, wird der aktuelle Teilstring zum neuen längsten Teilstring.

Abschließend gibt der Code eine Zeichenfolge und eine Ganzzahl k ein, ruft die Funktion longest_substring_bruteforce auf, um die längste Teilzeichenfolge mit k eindeutigen Vokalen zu finden, und gibt das Ergebnis aus.

#include <iostream>
#include <string>
#include <unordered_set>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

bool has_k_distinct_vowels(const std::string &s, int k) {
   std::unordered_set<char> vowel_set;
   for (char c : s) {
      if (is_vowel(c)) {
         vowel_set.insert(c);
      }
   }
   return vowel_set.size() == k;
}

std::string longest_substring_bruteforce(const std::string &s, int k) {
   std::string longest_substring = "";
   int max_len = 0;

   for (int i = 0; i < s.size(); ++i) {
      for (int j = i; j < s.size(); ++j) {
         std::string current_substring = s.substr(i, j - i + 1);
         if (has_k_distinct_vowels(current_substring, k) && current_substring.size() > max_len) {
         longest_substring = current_substring;
         max_len = current_substring.size();
         }
      }
   }

   return longest_substring;
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_bruteforce(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

Ausgabe

Longest substring with 3 distinct vowels: iaaioooaa

Methode 2: Schiebefenster

Die Sliding-Window-Methode ist eine Technik zur Lösung von Informatik- und Algorithmenproblemen. Es wird verwendet, um ein bestimmtes Muster zu finden, beispielsweise einen Teilstring oder ein Subarray, das bestimmte Kriterien in einer bestimmten Eingabe erfüllt.

Bei dieser Methode werden zwei Zeiger verwendet, um ein Schiebefenster zu erstellen, das je nach Eingabe gleitet. Die Größe des Fensters wird bei Bedarf angepasst, um sicherzustellen, dass die erforderlichen Bedingungen erfüllt sind. Der Algorithmus verfolgt die Eigenschaften des aktuellen Fensters, wie z. B. die Anzahl der einzelnen Elemente, die Summe der Elemente usw.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Die Funktion

is_vowel ist eine Hilfsfunktion, die true zurückgibt, wenn das angegebene Zeichen ein Vokal ist (d. h. a, e, i, o oder u).

Die Hauptfunktion longest_substring_slidingwindow akzeptiert die Zeichenfolge s und die Ganzzahl k als Eingabe. Es verwendet zwei Zeiger nach links und rechts, um ein Schiebefenster zu erstellen und über die Zeichenfolge zu iterieren.

Verwenden Sie die ungeordnete Kartenfrequenz, um die Häufigkeit jedes Vokals im aktuellen Fenster zu verfolgen. Wenn die Häufigkeit eines Vokals im Fenster k überschreitet, bewegen Sie den linken Zeiger nach rechts, bis die Häufigkeit des Vokals wieder gleich k ist. Die Länge des aktuellen Fensters wird als rechts - links + 1 berechnet. Wenn sie größer als die bisher gesehene maximale Länge ist, werden der Startindex und die Länge aktualisiert.

Schließlich gibt die Funktion mithilfe der substr-Methode der String-Klasse den längsten Teilstring mit k verschiedenen Vokalen zurück.

#include <iostream>
#include <string>
#include <unordered_map>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

std::string longest_substring_slidingwindow(const std::string &s, int k) {
   int left = 0, right = 0, max_len = 0, start = 0;
   std::unordered_map<char, int> freq;

   while (right < s.size()) {
      char c = s[right];
      if (is_vowel(c)) {
         freq[c]++;
      }

      while (freq.size() > k) {
         char left_char = s[left];
         if (is_vowel(left_char)) {
            freq[left_char]--;
            if (freq[left_char] == 0) {
               freq.erase(left_char);
            }
         }
         left++;
      }

      if (freq.size() == k && (right - left + 1) > max_len) {
         max_len = right - left + 1;
         start = left;
      }

      right++;
   }

   return s.substr(start, max_len);
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_slidingwindow(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

输出

Longest substring with 3 distinct vowels: iaaioooaa

结论

在本文中，我们讨论了两种方法来解决在给定字符串中找到包含K个不同元音字母的最长子串的问题。第一种方法是暴力法，而第二种方法是滑动窗口法。暴力法的时间复杂度为O(n^3)，使其成为更适合处理较大输入的解决方案。滑动窗口法由于其较低的时间复杂度，推荐用于解决这个问题。

Das obige ist der detaillierte Inhalt vonDer längste Teilstring mit K verschiedenen Vokalen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!