Remove Vowels

Q: Wie hoch ist die Zeitkomplexität beim Entfernen von Vokalen?

Ein Durchlauf benötigt O(n) Zeit, da für jedes Zeichen ein Vokaltest mit konstanter Laufzeit durchgeführt wird. Die Ausgabe benötigt im schlimmsten Fall O(n) Speicherplatz, wenn s überhaupt keine Vokale enthält. replace einmal pro Vokal aufzurufen ist ebenfalls O(n) , liest die Zeichenkette jedoch zehnmal.

Q: Kannst du Vokale mit einem regulären Ausdruck entfernen?

Ja. Das Muster [aeiouAEIOU] durch eine leere Zeichenfolge zu ersetzen, erledigt das in den meisten Sprachen mit einem Aufruf. Es läuft in O(n) , genauso wie die Schleife, aber Interviewer bitten dich normalerweise, die Schleife zu schreiben, damit sie den Vokaltest und den Aufbau des Ergebnisses sehen können.

EinsteigerArrays und Strings

+10

Du erhältst eine Zeichenfolge s, die aus englischen Buchstaben besteht. Gib die Zeichenfolge zurück, die du erhältst, wenn du jeden Vokal daraus entfernst. Die Vokale sind a, e, i, o und u, jeweils in Klein- oder Großschreibung; y ist hier kein Vokal. Die übrigen Buchstaben behalten ihre Reihenfolge und Groß- bzw. Kleinschreibung.

Funktion

removeVowels(s: string) → string

sstring: die Zeichenfolge englischer Buchstaben, die bereinigt werden soll
Gibt zurückstring: s, bei dem jeder Vokal entfernt wurde und die übrigen Buchstaben in ihrer ursprünglichen Reihenfolge stehen

Einschränkungen

1 ≤ s.length ≤ 3 × 10⁴
s enthält nur englische Buchstaben (a bis z, A bis Z).
s enthält mindestens einen Buchstaben, der kein Vokal ist, daher ist die Antwort nie leer.

Beispiele

Eingabe: s = "Interview"
Ausgabe: "ntrvw"
Erklärung: Wenn man I, e, i und e aus Interview entfernt, bleiben n, t, r, v, w in dieser Reihenfolge übrig. Das große I ist ebenfalls ein Vokal, also wird es entfernt.

Eingabe: s = "rhythm"
Ausgabe: "rhythm"
Erklärung: rhythm enthält kein a, e, i, o oder u, daher wird nichts gelöscht. Sein y steht nicht auf der Liste der Vokale und bleibt erhalten.

Eingabe: s = "EuropeanUnion"
Ausgabe: "rpnnn"
Erklärung: Acht der dreizehn Buchstaben von EuropeanUnion sind Vokale, einschließlich der Großbuchstaben E und U. Die fünf verbleibenden Konsonanten, r, p, n, n, n, behalten ihre Reihenfolge bei und ergeben rpnnn.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Was wäre, wenn der Text jeden beliebigen Unicode-Buchstaben enthalten könnte, etwa É oder ö? Welche davon sind Vokale, und wie ändert sich dein Test?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Zeichen aus der Mitte einer Zeichenfolge zu entfernen, ist teuer, wenn du sie einzeln löschst, weil alles hinter der Lücke nachrückt. Besser ist es, stattdessen die Antwort aufzubauen: Gehe die Zeichenfolge einmal durch und kopiere jeden Buchstaben, der kein Vokal ist. Wichtig sind dabei die Großbuchstaben unter den Vokalen und der Zusammenbau des Ergebnisses.

Lösche jeden Vokal in einem eigenen Durchlauf

Idee

Die meisten Sprachen können alle Vorkommen eines Zeichens aus einer Zeichenkette mit einem einzigen Aufruf löschen: Ersetze es durch nichts. Mach das zehnmal, einmal für jedes von a e i o u A E I O U, und es bleibt kein Vokal übrig. Die Konsonanten werden nie angetastet, daher behalten sie ihre Reihenfolge und Groß- und Kleinschreibung bei.

Bei Interview ergibt der Durchlauf für e Intrviw, der Durchlauf für i ergibt Intrvw und der Durchlauf für I ergibt ntrvw. Die anderen sieben Durchläufe finden nichts zum Entfernen.

Jeder Durchlauf liest die gesamte aktuelle Zeichenkette, daher beträgt der Aufwand etwa 10n Zeichenschritte. Das ist immer noch O(n), weil zehn eine Konstante ist, aber bei 3 × 10^4 Buchstaben bedeutet es 3 × 10^5 Schritte, während ein einziger Durchlauf 3 × 10^4 benötigt.

Algorithmus

Nimm die zehn Vokalbuchstaben aeiouAEIOU einzeln nacheinander.
Ersetze bei jedem davon jedes Vorkommen in s durch nichts.
Gib nach den zehn Durchläufen zurück, was von s übrig ist.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

Ein Durchgang, der die Konsonanten beibehält

Idee

Ändere die Aufgabe: Sammle alles andere, statt Vokale zu löschen. Durchlaufe s einmal und prüfe für jedes Zeichen, ob es zu den zehn Vokalbuchstaben gehört. Wenn nicht, hänge es an das Ergebnis an. Da du die Zeichen in der Reihenfolge anhängst, in der du sie liest, und kein Zeichen veränderst, bleiben Reihenfolge und Groß- und Kleinschreibung der Konsonanten genau wie im Original.

Bei EuropeanUnion überspringt der Durchlauf E, u, o, e, a, U, i und o und hängt r, p, n, n, n an: Das Ergebnis ist rpnnn.

Für jedes Zeichen fällt ein Test mit konstanter Laufzeit an (eine Suche in einer Menge, ein switch oder eine Suche in einer Zeichenkette mit zehn Buchstaben), daher beträgt die Laufzeit O(n). Sammle die Buchstaben in einem Builder oder einer Liste und wandle sie am Ende einmal in eine Zeichenkette um; eine unveränderliche Zeichenkette mit += zu erweitern, würde sie bei jedem Schritt kopieren. Die Ausgabe selbst benötigt O(n) Speicherplatz.

Algorithmus

Erstelle einen leeren Builder für das Ergebnis.
Gehe s Zeichen für Zeichen durch.
Wenn das Zeichen keines aus aeiouAEIOU ist, füge es dem Builder hinzu.
Gib den Builder als Zeichenfolge zurück.

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen durch die Vokalprüfung oder dadurch, wie die Ergebniszeichenfolge wächst.

Großgeschriebene Vokale vergessen. Wenn du nur aeiou prüfst, wird aus Interview Intrvw statt ntrvw. Prüfe alle zehn Buchstaben oder wandle das Zeichen vor der Prüfung in Kleinbuchstaben um, und behalte das ursprüngliche Zeichen in der Ausgabe bei.
Die Groß- und Kleinschreibung der beibehaltenen Buchstaben ändern. Wenn du die ganze Zeichenfolge in Kleinbuchstaben umwandelst, um die Prüfung zu vereinfachen, wird aus QUEUEING qng statt QNG. Wandle nur die Kopie, die du prüfst, in Kleinbuchstaben um und füge das ursprüngliche Zeichen hinzu.
Beim Vorwärtslaufen nach Index löschen. Wenn du s[i] entfernst, rückt der nächste Buchstabe an die Position i, und dann überspringt i++ ihn. So wird aus aab ab. Erstelle eine neue Zeichenfolge oder verwende getrennte Lese- und Schreibpositionen.
Eine unveränderliche Zeichenfolge in einer Schleife mit += verlängern. In Java oder C# wird bei jedem Schritt die gesamte Zeichenfolge kopiert: etwa 4.5 × 10^8 Zeichenkopien bei 3 × 10^4 Buchstaben. Verwende einen Builder oder eine Liste und füge die Elemente einmal am Ende zusammen.

Häufige Fragen4

Wie entfernt man Vokale aus einer Zeichenkette?

Durchlaufe die Zeichenkette einmal und kopiere jeden Buchstaben, der weder a, e, i, o noch u ist (unabhängig von der Groß- und Kleinschreibung), in einen Builder oder eine Liste. Füge sie am Ende zu einer Zeichenkette zusammen. Die Reihenfolge und Groß- und Kleinschreibung der beibehaltenen Buchstaben bleiben unverändert.

Wie hoch ist die Zeitkomplexität beim Entfernen von Vokalen?

Ein Durchlauf benötigt O(n) Zeit, da für jedes Zeichen ein Vokaltest mit konstanter Laufzeit durchgeführt wird. Die Ausgabe benötigt im schlimmsten Fall O(n) Speicherplatz, wenn s überhaupt keine Vokale enthält. replace einmal pro Vokal aufzurufen ist ebenfalls O(n), liest die Zeichenkette jedoch zehnmal.

Kannst du Vokale mit einem regulären Ausdruck entfernen?

Ja. Das Muster [aeiouAEIOU] durch eine leere Zeichenfolge zu ersetzen, erledigt das in den meisten Sprachen mit einem Aufruf. Es läuft in O(n), genauso wie die Schleife, aber Interviewer bitten dich normalerweise, die Schleife zu schreiben, damit sie den Vokaltest und den Aufbau des Ergebnisses sehen können.

Warum nicht die Vokale direkt aus der Zeichenkette löschen?

Wenn du ein Zeichen aus der Mitte löschst, rückt jedes spätere Zeichen nach links, sodass viele Löschungen O(n²) kosten können. Du kannst dies mit zwei Indizes in-place in O(n) erledigen: Einer liest jedes Zeichen, der andere schreibt den nächsten beizubehaltenden Buchstaben. In den meisten Sprachen können Strings jedoch nicht verändert werden, daher ist es naheliegend, einen neuen String zu erstellen.

Python

def removeVowels(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "Interview"

Erwartet

"ntrvw"