Count Vowels

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

O(n) , wobei n die Länge der Zeichenkette ist, da jedes Zeichen einmal mit höchstens fünf Buchstaben verglichen wird. Der zusätzliche Speicherplatz 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 Programmieraufgaben definieren die Vokale fast immer als a , e , i , o und u , und das ist auch hier der Fall. Wenn eine Aufgabe y einschließt, füge es zu den Buchstaben hinzu, die du überprüfst.

EinsteigerArrays und Strings

+10

Gib einen String s aus englischen Buchstaben an und gib zurück, wie viele seiner Zeichen Vokale sind. Die Vokale sind a, e, i, o und u, in Klein- oder Großbuchstaben. 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ßgeschriebene I zählt wie ein kleingeschriebenes, also lautet die Antwort 4.

Eingabe: s = "rhythm"
Ausgabe: 0
Erklärung: rhythm enthält kein a, e, i, o oder u, und y steht nicht auf der Liste, also ist die Antwort 0.

Weiterführende Frage

Kannst du zurückgeben, wie oft jeder der fünf Vokale vorkommt, während du die Zeichenfolge weiterhin nur einmal durchläufst?

Tipps

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

0 von 3 geöffnet

Lösung

Durchlaufe die Zeichenfolge einmal und verwende dabei einen Zähler. Wandle jedes Zeichen in Kleinbuchstaben um, sodass eine Prüfung auf die fünf Vokale beide Schreibweisen abdeckt.

Zähle jeden Vokal in einem eigenen Durchlauf

Idee

Zähle jeden der zehn Buchstaben in aeiouAEIOU mit einem eigenen Durchlauf über die Zeichenfolge und addiere anschließend die zehn Zählwerte. Jeder Vokal entspricht genau einem der zehn Buchstaben und wird daher einmal gezählt; kein Konsonant entspricht einem davon.

Die Zeichenfolge wird zehnmal gelesen. Das ist immer noch O(n), aber bei 5 × 10^4 Zeichen bedeutet das 5 × 10^5 Vergleiche, während ein Durchlauf jedes Zeichen einmal liest.

Algorithmus

Setze total = 0.
Nimm die zehn Buchstaben aeiouAEIOU nacheinander.
Durchlaufe für jeden Buchstaben die gesamte Zeichenfolge und addiere jedes Mal 1 zu total, wenn ein Zeichen diesem Buchstaben entspricht.
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

Lies den String einmal durch und prüfe für jedes Zeichen, ob es ein Vokal ist. Wenn du ihn zuerst in Kleinbuchstaben umwandelst, wird I zu i und Konsonanten bleiben Konsonanten. So vergleichst du mit fünf statt zehn Buchstaben.

Die Prüfung benötigt konstante Zeit: ein switch, eine Abfrage in einer Menge oder eine Suche im String aeiou. Jedes Zeichen wird einmal gelesen und es wird nur ein Zähler gespeichert: Zeitaufwand O(n), Speicherplatz O(1).

Algorithmus

Setze count = 0.
Gehe den String Zeichen für Zeichen durch.
Wandle das Zeichen in Kleinbuchstaben um.
Wenn es a, e, i, o oder u ist, erhöhe count um 1.
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

Nur Kleinbuchstaben prüfen. Ein Vergleich allein mit aeiou übersieht das große I in Interview und gibt 3 zurück.
y mitzählen. Hier ist es nie ein Vokal, daher ergibt rhythm 0.
Index 0 als Fehlschlag behandeln. "aeiou".indexOf('a') ist 0, also ein Treffer. Prüfe auf -1 oder vergleiche in PHP strpos mit false mithilfe von !==, denn dort gilt 0 == false.
strlen(s) in der Schleifenbedingung in C aufrufen. Dadurch wird der String bei jedem Schritt erneut durchlaufen, sodass 5 × 10^4 Zeichen etwa 2.5 × 10^9 Schritte kosten.

Häufige Fragen3

Wie zählt man die Vokale in einer Zeichenkette?

Durchlaufe die Zeichenfolge einmal mit einem Zähler. Wandle jedes Zeichen in Kleinbuchstaben um und addiere 1, wenn es a, e, i, o oder u ist. Wenn die Schleife endet, enthält der Zähler die Antwort.

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

O(n), wobei n die Länge der Zeichenkette ist, da jedes Zeichen einmal mit höchstens fünf Buchstaben verglichen wird. Der zusätzliche Speicherplatz 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 Programmieraufgaben definieren die Vokale fast immer als a, e, i, o und u, und das ist auch hier der Fall. Wenn eine Aufgabe y einschließt, füge es zu den Buchstaben hinzu, die du überprüfst.

def countVowels(s):
    # Schreibe hier den Code

Test #1

Test #2

Argument

s = "Interview"

Erwartete Ausgabe