Count Vowels

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

Es ist O(n) , wobei n die Länge der Zeichenfolge ist, da jedes Zeichen einmal überprüft wird und jede Überprüfung höchstens fünf Buchstaben vergleicht. Der zusätzliche Speicherbedarf beträgt O(1) : ein Zähler und die feste Menge der Vokale.

Q: Ist y in diesem Problem ein Vokal?

Nein. In der englischen Rechtschreibung fungiert y manchmal als Vokal, wie in rhythm , aber in Programmieraufgaben werden die Vokale fast immer als a , e , i , o und u definiert, und das ist auch hier der Fall. Wenn eine Aufgabe y einschließt, nimm es in die Buchstaben auf, die du überprüfst.

EinsteigerArrays und Strings

+10

Du erhältst eine Zeichenfolge s, die aus englischen Buchstaben besteht. Zähle, wie viele ihrer Zeichen Vokale sind, und gib diese Zahl zurück. Die Vokale sind a, e, i, o und u, in Klein- oder Großschreibung. Der Buchstabe y zählt nicht.

Funktion

countVowels(s: string) → integer

sstring: die Zeichenfolge englischer Buchstaben, die durchsucht werden soll
Gibt zurückinteger: die Anzahl der Vokale in s, Groß- und Kleinbuchstaben zusammen

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Buchstaben (a bis z, A bis Z).

Beispiele

Eingabe: s = "Interview"
Ausgabe: 4
Erklärung: Die Vokale sind I, e, i und e. Das große I zählt genauso wie ein kleines, also lautet die Antwort 4.

Eingabe: s = "rhythm"
Ausgabe: 0
Erklärung: rhythm enthält kein a, e, i, o oder u. Sein y klingt wie ein Vokal, steht aber nicht auf der Liste, daher lautet die Antwort 0.

+18 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du zurückgeben, wie oft jeder der fünf Vokale vorkommt, und dabei den String trotzdem nur einmal durchlaufen?

Tipps

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

0 von 3 geöffnet

Lösung

Das Zählen erfolgt in einem Durchlauf über den String mit einem Zähler. Die einzigen Entscheidungen sind, wie geprüft wird, ob ein Zeichen ein Vokal ist, und wie mit Großbuchstaben umgegangen wird. Wandle jedes Zeichen in einen Kleinbuchstaben um und vergleiche es mit den fünf Vokalen; für jedes Zeichen fällt ein konstanter Arbeitsaufwand an.

Zähle jeden Vokal in einem eigenen Durchlauf

Idee

Zerlege die Frage in zehn kleinere: Wie viele as gibt es, wie viele es und so weiter bis U. Jede davon ist eine einfache Zählung. Durchlaufe die Zeichenkette und addiere jeweils 1, wenn das Zeichen dem Buchstaben entspricht, nach dem du suchst. Addiere anschließend die zehn Zählungen.

Jeder Vokal in s entspricht genau einem der zehn Buchstaben in aeiouAEIOU, wird also genau einmal gezählt, und kein Konsonant entspricht einem davon. Bei Interview findet der Durchlauf für e 2 Treffer, der für i 1 Treffer, der für I 1 Treffer und die anderen sieben Durchläufe finden nichts: insgesamt 4.

Die Zeichenkette wird zehnmal gelesen, also gibt es etwa 10n Vergleiche. Das ist immer noch O(n), da zehn eine Konstante ist. Bei 5 × 10^4 Zeichen bedeutet das jedoch 5 × 10^5 Vergleiche, während ein einziger Durchlauf jedes Zeichen einmal lesen würde.

Algorithmus

Setze total = 0.
Nimm die zehn Buchstaben aeiouAEIOU einzeln nacheinander.
Durchlaufe für jeden Buchstaben die ganze Zeichenkette und addiere jedes Mal 1 zu total, wenn ein Zeichen mit ihm übereinstimmt.
Gib nach den zehn Durchläufen total zurück.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

Ein Durchlauf mit einer Prüfung auf Kleinbuchstaben

Idee

Drehe die Schleifen um. Lies den String einmal durch und stelle für jedes Zeichen eine Frage: Ist es ein Vokal? Damit du beide Fälle mit einer einzigen Prüfung abdecken kannst, wandle das Zeichen zuerst in Kleinbuchstaben um. I wird zu i und E zu e, während Konsonanten Konsonanten bleiben. So vergleichst du nur mit den fünf Buchstaben a, e, i, o und u.

Die Prüfung benötigt konstante Zeit: ein switch über fünf Buchstaben, eine Suche in einer Menge oder eine Suche im fünf Buchstaben langen String aeiou. Wenn du Interview durchgehst, erhöht sich der Zähler bei I, e, i und e und endet bei 4.

Jedes Zeichen wird einmal gelesen, daher beträgt die Laufzeit O(n). Der Speicherbedarf besteht aus dem Zähler und den fünf Vokalen: O(1) Speicher.

Algorithmus

Setze count = 0.
Gehe die Zeichenfolge Zeichen für Zeichen durch.
Wandle das Zeichen in Kleinbuchstaben um.
Wenn es a, e, i, o oder u ist, addiere 1 zu count.
Gib count zurück.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

Stolperfallen und Grenzfälle

Die Aufgabe lässt sich in wenigen Zeilen lösen, und die Fehler entstehen durch Fälle, die bei der ersten Prüfung übersehen werden.

Nur Kleinbuchstaben prüfen. Ein Vergleich ausschließlich mit aeiou übersieht das große I in Interview und gibt 3 zurück. Wandle das Zeichen in einen Kleinbuchstaben um oder liste alle zehn Buchstaben auf.
y mitzählen. In diesem Problem ist y nie ein Vokal, daher ergibt rhythm 0.
Index 0 als Nichttreffer behandeln. "aeiou".indexOf('a') ist 0, also ein Treffer. Prüfe auf -1 oder vergleiche in PHP strpos mit false, indem du !== verwendest, denn dort gilt 0 == false.
strlen(s) in der Schleifenbedingung in C aufrufen. Dabei wird bei jeder Iteration die gesamte Zeichenkette durchlaufen, sodass 5 × 10^4 Zeichen etwa 2.5 × 10^9 Schritte kosten. Beende die Schleife beim Terminator '\0' oder berechne die Länge einmal vor der Schleife.

Häufige Fragen4

Wie zählt man die Vokale in einer Zeichenkette?

Durchlaufe die Zeichenfolge einmal mit einem Zähler. Wandle jedes Zeichen in Kleinbuchstaben um und prüfe, ob es a, e, i, o oder u ist; wenn ja, erhöhe den Zähler um 1. Wenn die Schleife endet, enthält der Zähler die Antwort.

Wie hoch ist die Zeitkomplexität beim Zählen von Vokalen?

Es ist O(n), wobei n die Länge der Zeichenfolge ist, da jedes Zeichen einmal überprüft wird und jede Überprüfung höchstens fünf Buchstaben vergleicht. Der zusätzliche Speicherbedarf beträgt O(1): ein Zähler und die feste Menge der Vokale.

Ist y in diesem Problem ein Vokal?

Nein. In der englischen Rechtschreibung fungiert y manchmal als Vokal, wie in rhythm, aber in Programmieraufgaben werden die Vokale fast immer als a, e, i, o und u definiert, und das ist auch hier der Fall. Wenn eine Aufgabe y einschließt, nimm es in die Buchstaben auf, die du überprüfst.

Sollte die Prüfung auf Vokale eine Menge, eine switch-Anweisung oder eine Zeichenkettensuche verwenden?

Bei fünf Buchstaben benötigen alle drei pro Zeichen konstante Zeit, und der Geschwindigkeitsunterschied zwischen ihnen ist zu gering, um eine Rolle zu spielen. Wähle die Variante, die sich in deiner Sprache am besten liest: ein switch in C, C++ oder Go, eine Menge oder eine Suche in einer Zeichenkette in Python, JavaScript oder Ruby.

Python

def countVowels(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

s = "Interview"

Erwartet