Remove Vowels

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

Jedno przejście ma złożoność czasową O(n) , ponieważ dla każdego znaku wykonuje się jeden test sprawdzający, czy jest samogłoską, o stałej złożoności. Wynik zajmuje w najgorszym przypadku O(n) miejsca, gdy s nie zawiera żadnych samogłosek. Wywołanie replace raz dla każdej samogłoski również ma złożoność O(n) , ale odczytuje ciąg znaków dziesięć razy.

Q: Czy potrafisz usunąć samogłoski za pomocą wyrażenia regularnego?

Tak. Zastąpienie wzorca [aeiouAEIOU] pustym ciągiem znaków wystarczy, by zrobić to jednym wywołaniem w większości języków. Działa w czasie O(n) , tak samo jak pętla, ale osoby przeprowadzające rozmowę kwalifikacyjną zwykle proszą o napisanie pętli, aby mogły zobaczyć test samogłosek i sposób tworzenia wyniku.

PoczątkującyTablice i napisy

+10

Otrzymujesz ciąg znaków s składający się z angielskich liter. Zwróć ciąg znaków otrzymany przez usunięcie z niego każdej samogłoski. Samogłoski to a, e, i, o i u, małe lub wielkie; w tym przypadku y nie jest samogłoską. Pozostałe litery zachowują swoją kolejność i wielkość.

Funkcja

removeVowels(s: string) → string

sstring: ciąg angielskich liter do oczyszczenia
Zwracastring: s ze wszystkimi usuniętymi samogłoskami i pozostałymi literami w ich pierwotnej kolejności

Ograniczenia

1 ≤ s.length ≤ 3 × 10⁴
s zawiera tylko angielskie litery (a do z, A do Z).
s zawiera co najmniej jedną literę, która nie jest samogłoską, więc odpowiedź nigdy nie jest pusta.

Przykłady

Wejście: s = "Interview"
Wyjście: "ntrvw"
Wyjaśnienie: Usunięcie I, e, i i e z Interview pozostawia n, t, r, v, w w tej kolejności. Wielka litera I też jest samogłoską, więc ją usuwamy.

Wejście: s = "rhythm"
Wyjście: "rhythm"
Wyjaśnienie: rhythm nie zawiera a, e, i, o ani u, więc nic nie zostaje usunięte. Litera y nie znajduje się na liście samogłosek i pozostaje.

Wejście: s = "EuropeanUnion"
Wyjście: "rpnnn"
Wyjaśnienie: Osiem z trzynastu liter w EuropeanUnion to samogłoski, w tym wielkie litery E i U. Pozostałe pięć spółgłosek, r, p, n, n, n, zachowuje swoją kolejność i daje rpnnn.

Pytanie dodatkowe

Co jeśli tekst może zawierać dowolną literę Unicode, na przykład É lub ö? Które z nich są samogłoskami i jak zmienia się twój test?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Usuwanie znaków ze środka ciągu znaków jest kosztowne, jeśli robisz to po jednym znaku, ponieważ wszystko za luką przesuwa się. Lepszym rozwiązaniem jest zbudowanie wyniku: przejdź raz przez ciąg znaków i skopiuj każdą literę, która nie jest samogłoską. Trzeba pamiętać o wielkich literach będących samogłoskami oraz o tym, jak złożyć wynik.

Usuń każdą samogłoskę w osobnym przebiegu

Intuicja

Większość języków może usunąć wszystkie wystąpienia jednego znaku z ciągu w jednym wywołaniu: zastępując go pustym ciągiem. Zrób to dziesięć razy, po jednym razie dla każdego z a e i o u A E I O U, a nie zostanie żadna samogłoska. Spółgłoski nigdy nie są ruszane, więc zachowują swoją kolejność i wielkość liter.

Dla Interview przebieg dla e daje Intrviw, przebieg dla i daje Intrvw, a przebieg dla I daje ntrvw. Pozostałe siedem przebiegów nie znajduje niczego do usunięcia.

Każdy przebieg odczytuje cały bieżący ciąg, więc praca obejmuje około 10n kroków przetwarzania znaków. To nadal O(n), ponieważ dziesięć to stała, ale dla 3 × 10^4 liter oznacza to 3 × 10^5 kroków, podczas gdy pojedyncze przejście wymaga 3 × 10^4.

Algorytm

Bierz po kolei dziesięć liter samogłoskowych aeiouAEIOU.
Dla każdej z nich zamień wszystkie jej wystąpienia w s na nic.
Po dziesięciu przebiegach zwróć to, co zostało z s.

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

Jedno przejście, które zachowuje spółgłoski

Intuicja

Odwróć działanie: zamiast usuwać samogłoski, zbieraj wszystkie pozostałe znaki. Przejdź raz po s i dla każdego znaku sprawdź, czy jest jedną z dziesięciu liter oznaczających samogłoski. Jeśli nie jest, dołącz go do wyniku. Ponieważ dołączasz znaki w kolejności odczytu i nigdy ich nie zmieniasz, kolejność i wielkość liter spółgłosek w wyniku pozostają dokładnie takie jak w danych wejściowych.

W przypadku EuropeanUnion podczas przejścia pomijane są znaki E, u, o, e, a, U, i i o, a do wyniku dołączane są r, p, n, n, n: wynikiem jest rpnnn.

Każdy znak wymaga jednego testu o stałym czasie działania (wyszukania w zbiorze, użycia instrukcji switch lub wyszukania w ciągu dziesięciu liter), więc złożoność czasowa wynosi O(n). Zbieraj litery w obiekcie builder lub na liście, a na końcu zamień je na ciąg znaków; powiększanie niezmiennego ciągu za pomocą += powodowałoby jego kopiowanie na każdym kroku. Sam wynik zajmuje O(n) pamięci.

Algorytm

Utwórz pusty obiekt do budowania wyniku.
Przejdź przez s znak po znaku.
Jeśli znak nie jest jednym z aeiouAEIOU, dodaj go do obiektu.
Zwróć obiekt jako ciąg znaków.

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)

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z testu samogłosek albo ze sposobu, w jaki rośnie ciąg wynikowy.

Pomijanie wielkich liter oznaczających samogłoski. Sprawdzanie tylko aeiou zmienia Interview w Intrvw zamiast w ntrvw. Sprawdź wszystkie dziesięć liter albo zamień znak na małą literę przed testem, a w wyniku zachowaj oryginalny znak.
Zmiana wielkości liter w zachowanych znakach. Jeśli zamienisz cały ciąg na małe litery, aby skrócić test, QUEUEING zmieni się w qng zamiast w QNG. Zamień na małe litery tylko kopię, którą sprawdzasz, i dołącz oryginalny znak.
Usuwanie znaków podczas przechodzenia do przodu po indeksach. Usunięcie s[i] przesuwa następną literę na pozycję i, a potem i++ ją pomija, więc aab zmienia się w ab. Zbuduj nowy ciąg albo użyj osobnych pozycji odczytu i zapisu.
Rozbudowywanie niezmiennego ciągu za pomocą += w pętli. W Javie lub C# każdy krok kopiuje cały ciąg, co daje około 4.5 × 10^8 skopiowanych znaków dla 3 × 10^4 liter. Użyj obiektu do budowania ciągu lub listy, a następnie połącz jej elementy jeden raz.

Najczęstsze pytania3

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

Przejdź raz przez ciąg znaków i skopiuj każdą literę, która nie jest a, e, i, o ani u (niezależnie od wielkości), do obiektu budującego ciąg lub na listę. Na końcu połącz je w ciąg znaków. Kolejność i wielkość liter, które zostawisz, pozostają takie jak w oryginale.

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

Jedno przejście ma złożoność czasową O(n), ponieważ dla każdego znaku wykonuje się jeden test sprawdzający, czy jest samogłoską, o stałej złożoności. Wynik zajmuje w najgorszym przypadku O(n) miejsca, gdy s nie zawiera żadnych samogłosek. Wywołanie replace raz dla każdej samogłoski również ma złożoność O(n), ale odczytuje ciąg znaków dziesięć razy.

Czy potrafisz usunąć samogłoski za pomocą wyrażenia regularnego?

Tak. Zastąpienie wzorca [aeiouAEIOU] pustym ciągiem znaków wystarczy, by zrobić to jednym wywołaniem w większości języków. Działa w czasie O(n), tak samo jak pętla, ale osoby przeprowadzające rozmowę kwalifikacyjną zwykle proszą o napisanie pętli, aby mogły zobaczyć test samogłosek i sposób tworzenia wyniku.

def removeVowels(s):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

s = "Interview"

Oczekiwany wynik

"ntrvw"