Remove Vowels

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

Tek bir geçiş O(n) zaman alır, çünkü her karakter için sabit zamanlı bir ünlü kontrolü yapılır. En kötü durumda, s hiç ünlü içermediğinde çıktı O(n) alan kullanır. Her ünlü için bir kez replace çağırmak da O(n) zaman alır, ancak dizgeyi on kez okur.

Q: Ünlü harfleri düzenli ifade kullanarak kaldırabilir misin?

Evet. [aeiouAEIOU] desenini boş bir dizeyle değiştirmek, çoğu dilde bunu tek çağrıda yapar. O(n) zamanda çalışır; döngüyle aynı sürede. Ancak mülakatı yapanlar genellikle ünlü harf kontrolünü ve sonucu nasıl oluşturduğunu görebilmeleri için döngüyü yazmanı ister.

BaşlangıçDiziler ve dizgiler

+10

İngilizce harflerden oluşan bir s dizgesi verilir. İçindeki her sesli harfi silerek elde ettiğin dizgeyi döndür. Sesli harfler, küçük veya büyük harf olarak a, e, i, o ve u harfleridir; burada y sesli harf değildir. Kalan harfler sıralarını ve büyük-küçük harf durumlarını korur.

Fonksiyon

removeVowels(s: string) → string

sstring: temizlenecek İngilizce harf dizisi
Döndürürstring: s'nin tüm ünlüleri çıkarılmış ve diğer harfleri özgün sıralarında korunmuş hâli

Kısıtlar

1 ≤ s.length ≤ 3 × 10⁴
s yalnızca İngilizce harfleri (a ile z arası, A ile Z arası) içerir.
s en az bir ünsüz harf içerir, bu yüzden yanıt hiçbir zaman boş olmaz.

Örnekler

Girdi: s = "Interview"
Çıktı: "ntrvw"
Açıklama: Interview sözcüğünden I, e, i ve e harflerini silince, sırasıyla n, t, r, v, w kalır. Büyük I de bir ünlüdür, bu yüzden o da gider.

Girdi: s = "rhythm"
Çıktı: "rhythm"
Açıklama: rhythm sözcüğünde a, e, i, o veya u yoktur, bu yüzden hiçbir şey silinmez. İçindeki y ünlüler listesinde değildir ve kalır.

Girdi: s = "EuropeanUnion"
Çıktı: "rpnnn"
Açıklama: EuropeanUnion sözcüğündeki on üç harften sekizi, büyük E ve U dâhil olmak üzere sesli harftir. Geriye kalan beş sessiz harf, r, p, n, n, n, sıralarını korur ve rpnnn olarak okunur.

Gönderirken +17 gizli test

Ek soru

Metin, É veya ö gibi herhangi bir Unicode harfini içerebilseydi ne olurdu? Bunlardan hangileri sesli harftir ve testiniz nasıl değişir?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir dizenin ortasından karakterleri tek tek silmek maliyetlidir, çünkü boşluktan sonraki her şey kayar. Daha iyi yöntem, yanıtı oluşturmaktır: dizenin üzerinden bir kez geç ve sesli harf olmayan her harfi kopyala. Dikkat edilmesi gereken noktalar, büyük harfli sesli harfler ve sonucun nasıl bir araya getirileceğidir.

Her sesli harfi kendi geçişinde silin

Sezgi

Çoğu dil, bir karakterin dizgedeki tüm kopyalarını tek bir çağrıyla silebilir: onu hiçbir şeyle değiştirmeyerek. Bunu a e i o u A E I O U karakterlerinin her biri için bir kez olmak üzere on kez yapın; geriye hiçbir ünlü kalmaz. Ünsüzlere hiç dokunulmaz, bu yüzden sıraları ve büyük-küçük harf durumları korunur.

Interview için e turu Intrviw sonucunu verir, i turu Intrvw sonucunu verir ve I turu ntrvw sonucunu verir. Diğer yedi turda silinecek bir şey bulunmaz.

Her tur geçerli dizgenin tamamını okur, dolayısıyla işlem yaklaşık 10n karakter adımı gerektirir. Bu yine de O(n) olur, çünkü on bir sabittir; ancak 3 × 10^4 harf için bu, tek bir taramanın gerektirdiği 3 × 10^4 adıma karşılık 3 × 10^5 adım demektir.

Algoritma

On ünlü harfi aeiouAEIOU birer birer ele al.
Her biri için, s içindeki tüm kopyalarını hiçbir şeyle değiştir.
Bu on geçişten sonra s içinde kalanı döndür.

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

Ünsüzleri koruyan tek geçiş

Sezgi

İşi tersine çevir: ünlü harfleri silmek yerine geri kalan her şeyi topla. s üzerinde bir kez dolaş ve her karakter için bunun on ünlü harften biri olup olmadığını kontrol et. Değilse onu sonuca ekle. Okuma sırasına göre eklediğin ve hiçbir karakteri değiştirmediğin için ünsüzlerin sırası ve büyük-küçük harf durumu, girdidekiyle tamamen aynı olur.

EuropeanUnion için dolaşım E, u, o, e, a, U, i ve o harflerini atlar, r, p, n, n, n harflerini ekler: sonuç rpnnn olur.

Her karakter için sabit zamanlı bir kontrol yapılır (küme araması, bir switch veya on harflik bir dizgede arama), dolayısıyla süre O(n) olur. Harfleri bir oluşturucuda veya listede topla ve en sonda bir kez dizgeye dönüştür; değiştirilemez bir dizgeyi += ile büyütmek her adımda kopyalama yapar. Çıktının kendisi O(n) alan kullanır.

Algoritma

Sonuç için boş bir oluşturucu başlat.
s üzerinde her seferinde bir karakter ilerle.
Karakter aeiouAEIOU içindeki karakterlerden biri değilse, onu oluşturucuya ekle.
Oluşturucuyu bir dize olarak döndür.

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)

Tuzaklar ve uç durumlar

Çoğu yanlış yanıt, ünlü harf kontrolünden veya sonuç dizgesinin nasıl oluşturulduğundan kaynaklanır.

Büyük ünlü harfleri unutmak. Yalnızca aeiou harflerini kontrol etmek, Interview sözcüğünü ntrvw yerine Intrvw hâline getirir. On harfin tamamını kontrol et veya kontrol etmeden önce karakteri küçük harfe dönüştür ve özgün karakteri çıktıda koru.
Korunan harflerin büyük-küçük harf durumunu değiştirmek. Kontrolü kısaltmak için dizgenin tamamını küçük harfe dönüştürürsen QUEUEING, QNG yerine qng olarak döner. Yalnızca kontrol ettiğin kopyayı küçük harfe dönüştür ve özgün karakteri ekle.
Dizinde ileri doğru ilerlerken silme yapmak. s[i] öğesini kaldırmak, sonraki harfi i konumuna kaydırır; ardından i++ yaptığında o harfi atlarsın. Böylece aab, ab olarak döner. Yeni bir dizge oluştur veya ayrı okuma ve yazma konumlarıyla ilerle.
Döngüde += kullanarak değiştirilemez bir dizgeyi büyütmek. Java veya C#'ta her adım dizgenin tamamını kopyalar; 3 × 10^4 harf için yaklaşık 4.5 × 10^8 karakter kopyalanır. Bir oluşturucu veya liste kullanıp bir kez birleştir.

Sıkça sorulan sorular4

Bir dizgeden ünlü harfleri nasıl kaldırırsınız?

Dizgenin üzerinden bir kez geç ve büyük ya da küçük harf olmasına bakmadan a, e, i, o veya u olmayan her harfi bir oluşturucuya ya da listeye kopyala. Sonunda bunları bir dizgede birleştir. Korunan harflerin sırası ve büyük-küçük harf durumu olduğu gibi kalır.

Sesli harfleri kaldırmanın zaman karmaşıklığı nedir?

Tek bir geçiş O(n) zaman alır, çünkü her karakter için sabit zamanlı bir ünlü kontrolü yapılır. En kötü durumda, s hiç ünlü içermediğinde çıktı O(n) alan kullanır. Her ünlü için bir kez replace çağırmak da O(n) zaman alır, ancak dizgeyi on kez okur.

Ünlü harfleri düzenli ifade kullanarak kaldırabilir misin?

Evet. [aeiouAEIOU] desenini boş bir dizeyle değiştirmek, çoğu dilde bunu tek çağrıda yapar. O(n) zamanda çalışır; döngüyle aynı sürede. Ancak mülakatı yapanlar genellikle ünlü harf kontrolünü ve sonucu nasıl oluşturduğunu görebilmeleri için döngüyü yazmanı ister.

Ünlü harfleri neden dizenin içinden yerinde silmiyoruz?

Ortadaki bir karakteri silmek, sonraki tüm karakterleri sola kaydırır; bu nedenle çok sayıda silme işlemi O(n²) maliyetine yol açabilir. Bunu, her karakteri okuyan bir indeks ve sıradaki korunacak harfi yazan bir indeks kullanarak O(n) zamanda yerinde yapabilirsin; ancak çoğu dilde dizeler değiştirilemediğinden, yeni bir dize oluşturmak doğal bir çözümdür.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "Interview"

Beklenen

"ntrvw"