Valid Anagram

Q: Geçerli Anagram'ın zaman karmaşıklığı nedir?

Harfleri saymak O(n) zaman ve O(1) ek alan alır; çünkü dizelerin uzunluğu ne olursa olsun sayaç dizisinde 26 öğe bulunur. Her iki diziyi sıralamak O(n log n) zaman ve sıralanmış kopyalar için genellikle O(n) alan alır.

Q: Anagram kontrolü yaparken sıralamak mı yoksa saymak mı daha iyidir?

Sayma teorik olarak daha hızlıdır: O(n) , O(n log n) 'e kıyasla ve bir harf gereğinden fazla kullanıldığında hemen durabilir. Sıralama daha kısa yazılır ve herhangi bir alfabe için değişiklik gerektirmeden çalışır. Bir mülakatta önce sıralamadan bahset, ardından saymaya geçerek iyileştir.

KolayHashing Sıralama

+10

İki dizgeden biri diğerinin yeniden düzenlenmiş hâliyse anagramdır: aynı harfleri, her harften de aynı sayıda kullanırlar. Küçük İngilizce harflerden oluşan iki s ve t dizgesi veriliyor. t, s'nin anagramıysa true, değilse false döndürün.

Fonksiyon

isAnagram(s: string, t: string) → boolean

sstring: ilk dize, küçük harfler
tstring: s'ye karşı sınanacak dize
Döndürürboolean: t, s'deki harflerin her birini aynı sayıda kullanıyorsa true

Kısıtlar

1 ≤ s.length, t.length ≤ 2 × 10⁴
s ve t yalnızca küçük İngilizce harfler (a ile z arası) içerir.
İki uzunluk farklı olabilir.

Örnekler

Girdi: s = "listen"t = "silent"
Çıktı: true
Açıklama: Her iki kelimede de birer e, i, l, n, s ve t harfi bulunur; bu yüzden silent, harflerinin yeri değiştirilmiş hâliyle listen sözcüğüdür.

Girdi: s = "aabb"t = "abbb"
Çıktı: false
Açıklama: Uzunluklar eşleşiyor ve ikisi de yalnızca a ve b kullanıyor, ancak aabb içinde iki tane a, abbb içinde ise bir tane var. Yalnızca harflerin değil, sayıların da eşleşmesi gerekir.

Girdi: s = "cat"t = "cast"
Çıktı: false
Açıklama: cast dört harflidir ve cat üç harflidir, bu yüzden cat kelimesinin harflerini hiçbir şekilde yeniden düzenleyerek bunu yazamazsın.

Ek soru

Peki dizeler a'dan z'ye kadar olan karakterler yerine herhangi bir Unicode karakterini tutabilseydi? Sayımı nasıl değiştirirdin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir anagram harf sayılarını korur ve sıralamayı göz ardı eder. Bu yüzden harflerin nerede olduğunu unutan ama her birinden kaç tane olduğunu hatırlayan bir dize özeti gerekir. Sıralama bu özeti O(n log n) sürede oluşturur; 26 sayaçtan oluşan bir tablo ise tek geçişte oluşturur.

Her iki dizgeyi de sırala

Sezgi

Sıralama, bir dizgedeki harfleri alfabetik sıraya koyar ve her birinin başlangıçtaki konumunu siler. listen, eilnst olarak sıralanır; silent da aynı şekilde sıralandığından bunlar anagramdır. aabb, aabb olarak kalır ve abbb, abbb olarak kalır; 1. indekste farklı olduklarından anagram değildirler.

Test her iki yönde de çalışır. t, s'nin yeniden düzenlenmiş hâliyse ikisi de aynı harfleri aynı sayıda içerir, dolayısıyla sıralama aynı diziyi üretir. Sıralanmış diziler eşitse t, s'deki harflerin aynısını kullanır.

Önce uzunlukları karşılaştır: farklı uzunluktaki dizgeler asla anagram olmaz ve her iki sıralama işlemini de atlarsın. Sıralama O(n log n) zaman alır ve çoğu dil karakterlerin bir kopyasını sıralar; bu da O(n) ek alan gerektirir. n = 2 × 10^4 için bu hızlıdır, ancak sayma yaklaşımı daha az iş yapar.

Algoritma

s ve t uzunlukları farklıysa false döndür.
Her dizenin karakterlerini bir diziye kopyala.
Her iki diziyi de sırala.
Sıralanmış diziler eleman eleman eşitse true döndür.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Her harfi say

Sezgi

Yalnızca 26 harf görünebilir; bu yüzden 26 elemanlı bir dizide her harf için bir sayaç tutun: a için dizin 0, z için dizin 25 olsun. Bir harfin dizini, karakter kodundan a harfinin kodu çıkarılarak bulunur. s üzerinde ilerleyip her harfin sayacını 1 artırın, ardından t üzerinde ilerleyip 1 azaltın.

Erken durabilirsiniz: Bir sayacın 0'ın altına düşmesi, t içinde o harfin s içindekinden daha fazla kullanıldığı anlamına gelir. aabb ve abbb için s sonrasında sayaçlar a: 2 ve b: 2 değerini gösterir. Ardından t, b harfini üç kez alır; üçüncü seferde b -1 olur ve hemen false döndürürsünüz.

"Hiçbir sayaç negatif olmadı" demek neden yeterli? Dizelerin uzunlukları eşit olduğundan, her iki dolaşımın sonunda sayaçların toplamı 0 olur. Hiçbiri negatif değilse pozitif olan bir sayacı dengeleyecek bir değer olamaz; dolayısıyla tüm sayaçlar 0'dır ve harf sayıları eşleşir. Uzunluk kontrolünün yalnızca bir kısayol değil, gerekli olmasının nedeni budur.

Her dize bir kez okunur; bu da O(n) zaman demektir. Dizi, uzunluk ne olursa olsun her zaman 26 sayı tutar; dolayısıyla ek alan O(1)'dir.

Algoritma

s ve t dizelerinin uzunlukları farklıysa false döndür.
26 sıfırdan oluşan bir dizi oluştur.
s içindeki her harf için sayacını 1 artır.
t içindeki her harf için sayacını 1 azalt; 0'ın altına düşerse false döndür.
true döndür.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu, harflerin kaç kez geçtiğine bakmak yerine hangi harflerin bulunduğunu kontrol etmekten veya uzunluk kontrolünü atlamaktan kaynaklanır.

Harf kümelerini karşılaştırmak. aabb ve abbb tam olarak aynı a ve b harflerini kullanır, ancak anagram değildir.
t içindeki her harfin üzerini çizmeden s içinde bir yerde bulunduğunu kontrol etmek. aab ve abb bu testi her iki yönde de geçer.
Sayma yönteminde uzunluk kontrolünü atlamak. s = ab ve t = a olduğunda hiçbir sayaç 0'ın altına düşmez, dolayısıyla kod yanlışlıkla true döndürür.
Sayaç dizisini ham karakter koduyla indekslemek. a 97'dir; bu, 26 elemanlı bir dizinin sınırını çok aşar. Önce a'nın kodunu çıkarın. Lua ve R'de, dizileri 1. indeksten başladığı için 1 ekleyin.

Sıkça sorulan sorular3

Geçerli Anagram'ın zaman karmaşıklığı nedir?

Harfleri saymak O(n) zaman ve O(1) ek alan alır; çünkü dizelerin uzunluğu ne olursa olsun sayaç dizisinde 26 öğe bulunur. Her iki diziyi sıralamak O(n log n) zaman ve sıralanmış kopyalar için genellikle O(n) alan alır.

Anagram kontrolü yaparken sıralamak mı yoksa saymak mı daha iyidir?

Sayma teorik olarak daha hızlıdır: O(n), O(n log n)'e kıyasla ve bir harf gereğinden fazla kullanıldığında hemen durabilir. Sıralama daha kısa yazılır ve herhangi bir alfabe için değişiklik gerektirmeden çalışır. Bir mülakatta önce sıralamadan bahset, ardından saymaya geçerek iyileştir.

Unicode karakterler içeren anagramları nasıl kontrol edersiniz?

26 sayaçtan oluşan diziyi, karakterden sayıya eşleme yapan bir hash map ile değiştirin. s içindeki her karakter için 1 ekleyin, t içindeki her karakter için 1 çıkarın ve her sayacın 0'da kaldığını kontrol edin. Dizeleri bayt bayt değil, karakterlerin tamamını okuyarak işleyin; böylece birkaç baytta saklanan bir karakter bir kez sayılır.

def isAnagram(s, t):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

s = "listen"
t = "silent"

Beklenen Çıktı

true