Count Vowels

Q: Berapa kompleksitas waktu untuk menghitung huruf vokal?

O(n) , dengan n sebagai panjang string, karena setiap karakter diperiksa satu kali terhadap paling banyak lima huruf. Ruang tambahan adalah O(1) : satu penghitung dan set vokal tetap.

Q: Apakah y termasuk huruf vokal dalam soal ini?

Tidak. Dalam ejaan bahasa Inggris, y terkadang berfungsi sebagai huruf vokal, seperti dalam rhythm , tetapi soal pemrograman hampir selalu mendefinisikan huruf vokal sebagai a , e , i , o , dan u , dan soal ini juga begitu. Jika soal menyertakan y , tambahkan huruf itu ke huruf-huruf yang kamu periksa.

PemulaArray dan string

+10

Diberikan string s yang terdiri dari huruf-huruf bahasa Inggris, kembalikan jumlah karakter yang berupa huruf vokal. Huruf vokal adalah a, e, i, o, dan u, baik dalam huruf kecil maupun huruf besar. Huruf y tidak dihitung.

Fungsi

countVowels(s: string) → integer

sstring: string huruf bahasa Inggris yang akan dipindai
Mengembalikaninteger: jumlah huruf vokal dalam s, baik huruf besar maupun kecil

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s hanya berisi huruf bahasa Inggris (a sampai z, A sampai Z).

Contoh

Input: s = "Interview"
Output: 4
Penjelasan: Huruf vokalnya adalah I, e, i, dan e. Huruf kapital I dihitung seperti huruf kecil, jadi jawabannya adalah 4.

Input: s = "rhythm"
Output: 0
Penjelasan: rhythm tidak memiliki a, e, i, o, atau u, dan y tidak ada dalam daftar, jadi jawabannya adalah 0.

Pertanyaan lanjutan

Bisakah kamu mengembalikan jumlah kemunculan masing-masing dari lima huruf vokal dengan membaca string hanya satu kali?

Petunjuk

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

0 dari 3 dibuka

Solusi

Baca string satu kali dengan penghitung. Ubah setiap karakter menjadi huruf kecil, sehingga satu pemeriksaan terhadap lima huruf vokal mencakup kedua jenis huruf.

Hitung setiap vokal dalam lintasan tersendiri

Intuisi

Hitung masing-masing dari sepuluh huruf dalam aeiouAEIOU dengan satu lintasan tersendiri pada string, lalu jumlahkan kesepuluh hitungan tersebut. Setiap vokal sama persis dengan salah satu dari sepuluh huruf itu, jadi dihitung satu kali, dan tidak ada konsonan yang sama dengan satu pun dari huruf tersebut.

String dibaca sepuluh kali. Kompleksitasnya tetap O(n), tetapi untuk 5 × 10^4 karakter, ini berarti 5 × 10^5 perbandingan, dengan satu lintasan membaca setiap karakter satu kali.

Algoritma

Tetapkan total = 0.
Ambil sepuluh huruf aeiouAEIOU satu per satu.
Untuk setiap huruf, telusuri seluruh string dan tambahkan 1 ke total setiap kali sebuah karakter sama dengannya.
Setelah sepuluh putaran, kembalikan total.

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

Satu lintasan dengan pemeriksaan huruf kecil

Intuisi

Baca string sekali dan tanyakan untuk setiap karakter apakah itu huruf vokal. Mengubahnya menjadi huruf kecil terlebih dahulu mengubah I menjadi i dan membiarkan konsonan tetap sebagai konsonan, sehingga kamu membandingkannya dengan lima huruf, bukan sepuluh.

Pemeriksaannya membutuhkan waktu konstan: sebuah switch, pencarian dalam set, atau pencarian dalam string aeiou. Setiap karakter dibaca sekali dan hanya sebuah penghitung yang disimpan: waktu O(n), ruang O(1).

Algoritma

Atur count = 0.
Telusuri string satu karakter setiap kali.
Ubah karakter menjadi huruf kecil.
Jika karakter itu a, e, i, o, atau u, tambahkan 1 ke count.
Kembalikan count.

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

Jebakan dan kasus tepi

Hanya memeriksa huruf kecil. Membandingkan hanya dengan aeiou melewatkan huruf kapital I pada Interview dan menghasilkan 3.
Menghitung y. Di sini, huruf tersebut tidak pernah menjadi huruf vokal, jadi rhythm menghasilkan 0.
Menganggap indeks 0 sebagai tidak cocok. "aeiou".indexOf('a') bernilai 0, yang berarti cocok. Uji apakah nilainya -1, atau di PHP bandingkan strpos dengan false menggunakan !==, karena 0 == false di sana.
Memanggil strlen(s) dalam kondisi perulangan di C. Fungsi tersebut memindai ulang string pada setiap langkah, jadi 5 × 10^4 karakter membutuhkan sekitar 2.5 × 10^9 langkah.

Pertanyaan yang sering diajukan3

Bagaimana cara menghitung huruf vokal dalam sebuah string?

Telusuri string satu kali dengan penghitung. Ubah setiap karakter menjadi huruf kecil dan tambahkan 1 jika karakter tersebut adalah a, e, i, o atau u. Saat perulangan berakhir, penghitung berisi jawabannya.

Berapa kompleksitas waktu untuk menghitung huruf vokal?

O(n), dengan n sebagai panjang string, karena setiap karakter diperiksa satu kali terhadap paling banyak lima huruf. Ruang tambahan adalah O(1): satu penghitung dan set vokal tetap.

Apakah y termasuk huruf vokal dalam soal ini?

Tidak. Dalam ejaan bahasa Inggris, y terkadang berfungsi sebagai huruf vokal, seperti dalam rhythm, tetapi soal pemrograman hampir selalu mendefinisikan huruf vokal sebagai a, e, i, o, dan u, dan soal ini juga begitu. Jika soal menyertakan y, tambahkan huruf itu ke huruf-huruf yang kamu periksa.

def countVowels(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

s = "Interview"

Output yang diharapkan