Count Vowels

Q: Jaka jest złożoność czasowa zliczania samogłosek?

Jest to O(n) , gdzie n oznacza długość ciągu znaków, ponieważ każdy znak jest sprawdzany raz, a każde sprawdzenie porównuje go z co najwyżej pięcioma literami. Dodatkowa pamięć zajmuje O(1) : jeden licznik i stały zestaw samogłosek.

Q: Czy y jest samogłoską w tym zadaniu?

Nie. W angielskiej pisowni y czasami pełni funkcję samogłoski, jak w słowie rhythm , ale w zadaniach programistycznych samogłoski są prawie zawsze definiowane jako a , e , i , o i u — i w tym zadaniu jest tak samo. Jeśli zadanie uwzględnia y , dodaj ją do sprawdzanych liter.

PoczątkującyTablice i napisy

+10

Otrzymujesz ciąg znaków s złożony z angielskich liter. Policz, ile jego znaków to samogłoski, i zwróć tę liczbę. Samogłoski to a, e, i, o i u, zapisane małymi lub wielkimi literami. Litera y się nie liczy.

Funkcja

countVowels(s: string) → integer

sstring: ciąg angielskich liter do przeskanowania
Zwracainteger: liczba samogłosek w s, łącznie z wielkimi i małymi literami

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera tylko angielskie litery (a do z, A do Z).

Przykłady

Wejście: s = "Interview"
Wyjście: 4
Wyjaśnienie: Samogłoski to I, e, i i e. Wielkie I liczy się tak samo jak małe, więc odpowiedź to 4.

Wejście: s = "rhythm"
Wyjście: 0
Wyjaśnienie: rhythm nie zawiera a, e, i, o ani u. Jego y brzmi jak samogłoska, ale nie ma go na liście, więc odpowiedź to 0.

+18 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz zwrócić, ile razy występuje każda z pięciu samogłosek, wciąż odczytując ciąg znaków tylko raz?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Liczenie wymaga jednego przejścia po ciągu znaków z użyciem licznika. Jedyne decyzje dotyczą tego, jak sprawdzić, czy znak jest samogłoską, i co zrobić z wielkimi literami. Zamień każdy znak na małą literę i porównaj go z pięcioma samogłoskami — każdy znak wymaga stałej ilości pracy.

Licz każdą samogłoskę w osobnym przebiegu

Intuicja

Podziel pytanie na dziesięć mniejszych: ile jest liter a, ile e i tak dalej aż do U. Każda z tych wartości to zwykła liczba wystąpień. Przejdź po ciągu znaków i dodaj 1 za każdym razem, gdy znak jest równy szukanej literze, a następnie zsumuj te dziesięć wartości.

Każda samogłoska w s jest dokładnie jedną z dziesięciu liter w aeiouAEIOU, więc jest liczona dokładnie raz, a żadna spółgłoska nie jest żadną z nich. Dla Interview przebieg zliczający e znajduje 2, przebieg zliczający i znajduje 1, przebieg zliczający I znajduje 1, a pozostałe siedem przebiegów niczego nie znajduje: łącznie 4.

Ciąg znaków jest odczytywany dziesięć razy, czyli wykonuje się około 10n porównań. To nadal O(n), ponieważ dziesięć jest stałą, ale dla 5 × 10^4 znaków oznacza to 5 × 10^5 porównań, podczas gdy jeden przebieg odczytałby każdy znak tylko raz.

Algorytm

Ustaw total = 0.
Weź kolejno dziesięć liter aeiouAEIOU.
Dla każdej litery przejdź przez cały ciąg znaków i za każdym razem, gdy znak jest jej równy, zwiększ total o 1.
Po dziesięciu przejściach zwróć total.

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

Jedno przejście ze sprawdzaniem małych liter

Intuicja

Odwróć pętle. Przeczytaj ciąg znaków raz i dla każdego znaku zadaj jedno pytanie: czy to samogłoska? Aby objąć oba przypadki za pomocą jednego sprawdzenia, najpierw zamień znak na małą literę. I zamienia się w i, a E w e, natomiast spółgłoski pozostają spółgłoskami, więc porównujesz tylko z pięcioma literami: a, e, i, o i u.

Sprawdzenie zajmuje stały czas: switch dla pięciu liter, wyszukiwanie w zbiorze albo wyszukiwanie w pięcioznakowym ciągu aeiou. Podczas przechodzenia przez Interview licznik zwiększa się przy I, e, i i e, a na końcu wynosi 4.

Każdy znak jest odczytywany raz, więc złożoność czasowa wynosi O(n). Pamięć zajmują licznik i pięć samogłosek, czyli złożoność pamięciowa wynosi O(1).

Algorytm

Ustaw count = 0.
Przejdź przez ciąg znaków, znak po znaku.
Zamień znak na małą literę.
Jeśli jest to a, e, i, o lub u, zwiększ count o 1.
Zwróć count.

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

Pułapki i przypadki brzegowe

To zadanie można rozwiązać w kilku wierszach, a błędy wynikają z przypadków, o których zapomina pierwsze sprawdzenie.

Sprawdzanie tylko małych liter. Porównanie wyłącznie z aeiou pomija wielką literę I w Interview i zwraca 3. Zamień znak na małą literę albo wypisz wszystkie dziesięć liter.
Liczenie y. W tym zadaniu y nigdy nie jest samogłoską, więc rhythm daje 0.
Traktowanie indeksu 0 jako braku dopasowania. "aeiou".indexOf('a') zwraca 0, co oznacza dopasowanie. Sprawdzaj, czy wynikiem jest -1, albo w PHP porównuj strpos z false za pomocą !==, ponieważ 0 == false jest tam prawdziwe.
Wywoływanie strlen(s) w warunku pętli w C. Funkcja przechodzi przez cały ciąg przy każdej iteracji, więc 5 × 10^4 znaków wymaga około 2.5 × 10^9 kroków. Zatrzymuj się na terminatorze '\0' albo oblicz długość raz przed pętlą.

Najczęstsze pytania4

Jak policzyć samogłoski w ciągu znaków?

Przejdź przez ciąg znaków jeden raz, używając licznika. Zamień każdy znak na małą literę i sprawdź, czy jest to a, e, i, o lub u; jeśli tak, dodaj 1. Po zakończeniu pętli licznik zawiera odpowiedź.

Jaka jest złożoność czasowa zliczania samogłosek?

Jest to O(n), gdzie n oznacza długość ciągu znaków, ponieważ każdy znak jest sprawdzany raz, a każde sprawdzenie porównuje go z co najwyżej pięcioma literami. Dodatkowa pamięć zajmuje O(1): jeden licznik i stały zestaw samogłosek.

Czy y jest samogłoską w tym zadaniu?

Nie. W angielskiej pisowni y czasami pełni funkcję samogłoski, jak w słowie rhythm, ale w zadaniach programistycznych samogłoski są prawie zawsze definiowane jako a, e, i, o i u — i w tym zadaniu jest tak samo. Jeśli zadanie uwzględnia y, dodaj ją do sprawdzanych liter.

Czy do sprawdzania samogłosek użyć zbioru, instrukcji switch czy wyszukiwania w ciągu znaków?

W przypadku pięciu liter wszystkie trzy rozwiązania mają stały czas działania dla każdego znaku, a różnica szybkości między nimi jest zbyt mała, by miała znaczenie. Wybierz to, które najlepiej czyta się w Twoim języku: instrukcję switch w C, C++ lub Go, zbiór albo wyszukiwanie w ciągu znaków w Pythonie, JavaScript lub Ruby.

Python

def countVowels(s):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

s = "Interview"

Oczekiwane