Count Vowels

Q: Sesli harfleri saymanın zaman karmaşıklığı nedir?

O(n) ; burada n dizenin uzunluğudur, çünkü her karakter en fazla beş harfe karşı bir kez kontrol edilir. Ek alan O(1) 'dir: bir sayaç ve sabit ünlü kümesi.

Q: Bu problemde y bir sesli harf midir?

Hayır. İngilizce yazımında y bazen rhythm sözcüğünde olduğu gibi ünlü harf görevi görür, ancak programlama problemleri ünlü harfleri neredeyse her zaman a , e , i , o ve u olarak tanımlar; bu problemde de öyle. Bir problem y harfini içeriyorsa, onu kontrol ettiğin harflere ekle.

BaşlangıçDiziler ve dizgiler

+10

İngilizce harflerden oluşan bir s dizgesi verildiğinde, karakterlerinden kaçının sesli harf olduğunu döndür. Sesli harfler, küçük veya büyük harfle yazılmış a, e, i, o ve u harfleridir. y harfi sayılmaz.

Fonksiyon

countVowels(s: string) → integer

sstring: Taranacak İngilizce harf dizisi
Döndürürinteger: s içindeki sesli harflerin sayısı; büyük ve küçük harfler birlikte

Kısıtlar

1 ≤ s.length ≤ 5 × 10⁴
s yalnızca İngilizce harfler içerir (a'dan z'ye, A'dan Z'ye).

Örnekler

Girdi: s = "Interview"
Çıktı: 4
Açıklama: Ünlüler I, e, i ve e harfleridir. Büyük I küçük harf gibi sayılır, dolayısıyla cevap 4'tür.

Girdi: s = "rhythm"
Çıktı: 0
Açıklama: rhythm sözcüğünde a, e, i, o veya u yok ve y listede yer almıyor, bu yüzden cevap 0.

Ek soru

Beş ünlünün her birinin kaç kez geçtiğini, dizeyi yalnızca bir kez okuyarak yine de döndürebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Dizgeyi bir sayaçla bir kez oku. Her karakteri küçük harfe dönüştür; böylece beş sesli harfe karşı yapılan tek bir kontrol her iki durumu da kapsar.

Her sesli harfi kendi geçişinde say

Sezgi

aeiouAEIOU içindeki on harfin her birini dizgeyi bir kez tarayarak sayın, ardından bu on sayımı toplayın. Her sesli harf bu on harften tam olarak birine eşittir, dolayısıyla bir kez sayılır; hiçbir sessiz harf de bunlardan herhangi birine eşit değildir.

Dizge on kez okunur. Bu yine de O(n) değerindedir, ancak 5 × 10^4 karakter için, her karakterin bir kez okunduğu tek bir taramaya kıyasla 5 × 10^5 karşılaştırma anlamına gelir.

Algoritma

total = 0 olarak ayarla.
aeiouAEIOU içindeki on harfi teker teker al.
Her harf için dizgenin tamamını tara ve her karakter ona eşit olduğunda total değerini 1 artır.
On geçişten sonra total değerini döndür.

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

Küçük harf kontrolüyle tek geçiş

Sezgi

Dizeyi bir kez okuyun ve her karakterin sesli harf olup olmadığını kontrol edin. Önce küçük harfe dönüştürmek, I karakterini i yapar ve ünsüzleri ünsüz olarak bırakır; böylece on harf yerine beş harfle karşılaştırma yaparsınız.

Kontrol sabit zaman alır: bir switch, küme araması veya aeiou dizesinde arama. Her karakter bir kez okunur ve yalnızca bir sayaç saklanır: O(n) zaman, O(1) alan.

Algoritma

count = 0 olarak ayarla.
Dizgide karakter karakter ilerle.
Karakteri küçük harfe dönüştür.
Eğer a, e, i, o veya u ise count değerini 1 artır.
count değerini döndür.

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

Tuzaklar ve uç durumlar

Yalnızca küçük harfleri kontrol etmek. Yalnızca aeiou ile karşılaştırmak, Interview sözcüğündeki büyük I harfini gözden kaçırır ve 3 sonucunu verir.
y harfini saymak. Burada bu harf hiçbir zaman sesli harf değildir; bu nedenle rhythm 0 sonucunu verir.
0 indeksini eşleşme değilmiş gibi değerlendirmek. "aeiou".indexOf('a') 0 değerini verir ve bu bir eşleşmedir. -1 değerini kontrol edin veya PHP'de strpos sonucunu false ile !== kullanarak karşılaştırın; çünkü orada 0 == false olur.
C'de döngü koşulunda strlen(s) çağırmak. Bu, her adımda dizgeyi yeniden tarar; dolayısıyla 5 × 10^4 karakter yaklaşık 2.5 × 10^9 adım gerektirir.

Sıkça sorulan sorular3

Bir string içindeki ünlüleri nasıl sayarsın?

Bir sayaçla dizgede bir kez ilerle. Her karakteri küçük harfe dönüştür ve a, e, i, o veya u ise sayacı 1 artır. Döngü sona erdiğinde sayaç yanıtı tutar.

Sesli harfleri saymanın zaman karmaşıklığı nedir?

O(n); burada n dizenin uzunluğudur, çünkü her karakter en fazla beş harfe karşı bir kez kontrol edilir. Ek alan O(1)'dir: bir sayaç ve sabit ünlü kümesi.

Bu problemde y bir sesli harf midir?

Hayır. İngilizce yazımında y bazen rhythm sözcüğünde olduğu gibi ünlü harf görevi görür, ancak programlama problemleri ünlü harfleri neredeyse her zaman a, e, i, o ve u olarak tanımlar; bu problemde de öyle. Bir problem y harfini içeriyorsa, onu kontrol ettiğin harflere ekle.

def countVowels(s):
    # Kodu buraya yazın

Test #1

Test #2

Argüman

s = "Interview"

Beklenen Çıktı