Remove Vowels

Q: Apa kompleksitas waktu untuk menghapus huruf vokal?

Satu kali lintasan membutuhkan waktu O(n) , karena setiap karakter menjalani satu pengujian vokal dengan waktu konstan. Output membutuhkan ruang O(n) dalam kasus terburuk, saat s tidak memiliki vokal sama sekali. Memanggil replace sekali untuk setiap vokal juga membutuhkan waktu O(n) , tetapi cara ini membaca string sepuluh kali.

Q: Bisakah kamu menghapus huruf vokal dengan ekspresi reguler?

Ya. Mengganti pola [aeiouAEIOU] dengan string kosong dapat melakukannya dalam satu pemanggilan di sebagian besar bahasa. Proses ini berjalan dalam O(n) , sama seperti perulangan, tetapi pewawancara biasanya memintamu menulis perulangan agar mereka dapat melihat pengujian vokal dan cara kamu membangun hasilnya.

PemulaArray dan string

+10

Kamu mendapatkan string s yang terdiri dari huruf-huruf bahasa Inggris. Kembalikan string yang diperoleh setelah menghapus setiap huruf vokal darinya. Huruf vokalnya adalah a, e, i, o, dan u, dalam huruf kecil atau huruf besar; y bukan huruf vokal di sini. Huruf yang tersisa tetap dalam urutan dan bentuk huruf yang sama.

Fungsi

removeVowels(s: string) → string

sstring: string huruf bahasa Inggris yang perlu dibersihkan
Mengembalikanstring: s dengan semua huruf vokal dihapus dan huruf lainnya tetap dalam urutan aslinya

Batasan

1 ≤ s.length ≤ 3 × 10⁴
s hanya berisi huruf bahasa Inggris (a sampai z, A sampai Z).
s berisi setidaknya satu huruf yang bukan vokal, jadi jawabannya tidak pernah kosong.

Contoh

Input: s = "Interview"
Output: "ntrvw"
Penjelasan: Menghapus I, e, i, dan e dari Interview menyisakan n, t, r, v, w dalam urutan tersebut. Huruf kapital I juga merupakan huruf vokal, jadi huruf itu dihapus.

Input: s = "rhythm"
Output: "rhythm"
Penjelasan: rhythm tidak memiliki a, e, i, o, atau u, jadi tidak ada yang dihapus. Huruf y-nya tidak ada dalam daftar huruf vokal dan tetap ada.

Input: s = "EuropeanUnion"
Output: "rpnnn"
Penjelasan: Delapan dari tiga belas huruf dalam EuropeanUnion adalah huruf vokal, termasuk huruf kapital E dan U. Lima huruf konsonan yang tersisa, r, p, n, n, n, tetap dalam urutannya dan membentuk rpnnn.

Pertanyaan lanjutan

Apa jadinya jika teks dapat berisi huruf Unicode apa pun, seperti É atau ö? Manakah di antaranya yang merupakan huruf vokal, dan bagaimana perubahan pengujianmu?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Menghapus karakter satu per satu dari tengah string menggeser semua karakter setelah setiap celah. Sebagai gantinya, susun jawabannya: telusuri string sekali dan salin setiap huruf yang bukan vokal. Pastikan vokal kapital ditangani dengan benar, lalu susun hasilnya dalam builder.

Hapus setiap vokal dalam lintasan tersendiri

Intuisi

Kebanyakan bahasa menghapus setiap salinan dari satu karakter dalam satu pemanggilan: ganti karakter itu dengan apa pun. Lakukan sekali untuk setiap karakter berikut: a e i o u A E I O U. Konsonan tidak pernah disentuh, jadi urutan dan huruf besarnya tetap sama. Untuk Interview, pemrosesan untuk e, i, dan I menghasilkan Intrviw, Intrvw, dan ntrvw; tujuh karakter lainnya tidak menemukan apa pun.

Setiap pemrosesan membaca seluruh string, sekitar 10n langkah secara total. Itu tetap O(n), tetapi untuk 3 × 10^4 huruf, jumlahnya 3 × 10^5 langkah, sementara satu kali pemindaian hanya membutuhkan 3 × 10^4 langkah.

Algoritma

Ambil sepuluh huruf vokal aeiouAEIOU satu per satu.
Untuk setiap huruf, ganti semua kemunculannya di s dengan string kosong.
Setelah sepuluh kali proses, kembalikan sisa s.

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

Satu kali lintasan yang mempertahankan konsonan

Intuisi

Kumpulkan karakter yang dipertahankan, bukan menghapus karakter yang dibuang. Telusuri s sekali, lalu tambahkan setiap karakter yang bukan salah satu dari sepuluh huruf vokal. Kamu menambahkan karakter sesuai urutan pembacaan dan tidak pernah mengubahnya, sehingga konsonan tetap mempertahankan urutan dan kapitalisasinya.

Setiap karakter memerlukan satu pengujian waktu konstan, seperti pencarian di set, switch, atau pencarian dalam string berisi sepuluh huruf, sehingga waktunya adalah O(n). Tambahkan karakter ke builder atau list, lalu ubah hasilnya menjadi string sekali di akhir. Output itu sendiri memerlukan ruang O(n).

Algoritma

Mulai builder kosong untuk hasilnya.
Telusuri s satu karakter setiap kali.
Jika karakter tersebut bukan salah satu dari aeiouAEIOU, tambahkan ke builder.
Kembalikan builder sebagai string.

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)

Jebakan dan kasus tepi

Lupa menyertakan huruf vokal kapital. Menguji hanya aeiou mengubah Interview menjadi Intrvw, bukan ntrvw.
Mengubah seluruh string menjadi huruf kecil untuk mempersingkat pengujian. QUEUEING kemudian menghasilkan qng, bukan QNG. Ubah hanya salinan yang kamu uji menjadi huruf kecil.
Menghapus sambil berjalan maju berdasarkan indeks. Menghapus s[i] menggeser huruf berikutnya ke posisi i, lalu i++ melewatinya, sehingga aab menghasilkan ab.
Memperpanjang string yang immutable dengan += dalam perulangan. Di Java atau C#, setiap langkah menyalin seluruh string, sekitar 4.5 × 10^8 penyalinan karakter untuk 3 × 10^4 huruf.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk menghapus huruf vokal?

Satu kali lintasan membutuhkan waktu O(n), karena setiap karakter menjalani satu pengujian vokal dengan waktu konstan. Output membutuhkan ruang O(n) dalam kasus terburuk, saat s tidak memiliki vokal sama sekali. Memanggil replace sekali untuk setiap vokal juga membutuhkan waktu O(n), tetapi cara ini membaca string sepuluh kali.

Bisakah kamu menghapus huruf vokal dengan ekspresi reguler?

Ya. Mengganti pola [aeiouAEIOU] dengan string kosong dapat melakukannya dalam satu pemanggilan di sebagian besar bahasa. Proses ini berjalan dalam O(n), sama seperti perulangan, tetapi pewawancara biasanya memintamu menulis perulangan agar mereka dapat melihat pengujian vokal dan cara kamu membangun hasilnya.

Mengapa tidak menghapus huruf vokal langsung dari string?

Menghapus satu karakter dari bagian tengah akan menggeser setiap karakter setelahnya ke kiri, sehingga banyak penghapusan dapat memerlukan biaya O(n²). Kamu bisa melakukannya langsung di tempat dalam O(n) dengan dua indeks, satu untuk membaca setiap karakter dan satu untuk menulis huruf berikutnya yang dipertahankan, tetapi di sebagian besar bahasa pemrograman, string tidak dapat diubah, jadi membuat string baru adalah cara yang wajar.

def removeVowels(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "Interview"

Output yang diharapkan

"ntrvw"