Count Vowels

Q: Czaka złożoność czasowa liczenia samogłosek?

O(n) , gdzie n to długość ciągu znaków, ponieważ każdy znak jest sprawdzany jeden raz pod kątem występowania wśród maksymalnie pięciu liter. Dodatkowe miejsce wynosi 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 prawie zawsze definiuje się jako a , e , i , o i u , i tak jest w tym zadaniu. Jeśli zadanie uwzględnia y , dodaj ją do sprawdzanych liter.

PoczątkującyTablice i napisy

+10

Mając ciąg znaków s składający się z liter alfabetu angielskiego, zwróć liczbę znaków będących samogłoskami. Samogłoski to a, e, i, o i u, małe lub wielkie. Litera y się nie liczy.

Funkcja

countVowels(s: string) → integer

sstring: ciąg angielskich liter do przeszukania
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. Wielka litera I liczy się tak samo jak mała, więc odpowiedź to 4.

Wejście: s = "rhythm"
Wyjście: 0
Wyjaśnienie: rhythm nie zawiera a, e, i, o ani u, a y nie ma na liście, więc odpowiedź wynosi 0.

Pytanie dodatkowe

Czy możesz zwrócić, ile razy występuje każda z pięciu samogłosek, 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

Odczytaj ciąg znaków jeden raz, używając licznika. Zamień każdy znak na małą literę, aby jedno sprawdzenie pięciu samogłosek obejmowało oba przypadki.

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

Intuicja

Policz każdą z dziesięciu liter w aeiouAEIOU podczas osobnego przejścia po ciągu znaków, a następnie dodaj te dziesięć wyników. Każda samogłoska jest dokładnie jedną z tych dziesięciu liter, więc zostaje policzona raz, a żadna spółgłoska nie jest żadną z nich.

Ciąg znaków jest odczytywany dziesięć razy. To nadal O(n), ale dla 5 × 10^4 znaków oznacza 5 × 10^5 porównań, podczas gdy jedno przejście odczytuje każdy znak raz.

Algorytm

Ustaw total = 0.
Weź dziesięć liter aeiouAEIOU, po jednej naraz.
Dla każdej litery przejdź przez cały ciąg znaków i dodaj 1 do total za każdym razem, gdy znak jest jej równy.
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 z kontrolą małych liter

Intuicja

Przeczytaj ciąg znaków raz i dla każdego znaku sprawdź, czy jest samogłoską. Zamiana na małe litery sprawia, że I zmienia się w i, a spółgłoski pozostają spółgłoskami, więc porównujesz znak z pięcioma literami zamiast z dziesięcioma.

Sprawdzenie zajmuje stały czas: switch, wyszukanie w zbiorze lub wyszukanie w ciągu aeiou. Każdy znak jest odczytywany raz i przechowywany jest tylko licznik: czas O(n), pamięć O(1).

Algorytm

Ustaw count = 0.
Przejdź przez ciąg 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

Sprawdzanie tylko małych liter. Porównywanie wyłącznie z aeiou pomija wielką literę I w Interview i zwraca 3.
Liczenie y. Tutaj 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 prawdą.
Wywoływanie strlen(s) w warunku pętli w C. Za każdym razem ponownie skanuje ciąg, więc 5 × 10^4 znaków wymaga około 2.5 × 10^9 kroków.

Najczęstsze pytania3

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 dodaj 1, jeśli jest to a, e, i, o lub u. Gdy pętla się zakończy, licznik będzie zawierał odpowiedź.

Czaka złożoność czasowa liczenia samogłosek?

O(n), gdzie n to długość ciągu znaków, ponieważ każdy znak jest sprawdzany jeden raz pod kątem występowania wśród maksymalnie pięciu liter. Dodatkowe miejsce wynosi 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 prawie zawsze definiuje się jako a, e, i, o i u, i tak jest w tym zadaniu. Jeśli zadanie uwzględnia y, dodaj ją do sprawdzanych liter.

def countVowels(s):
    # Napisz tutaj kod

Test #1

Test #2

Argument

s = "Interview"

Oczekiwany wynik