Leetcode 242 Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false

Bu fonksiyon nasıl çalışır:

Uzunluk Kontrolü: Öncelikle, iki stringin uzunluklarını kontrol eder. Eğer uzunluklar farklıysa, stringler anagram olamaz, çünkü anagramlar aynı harf frekanslarına sahip olmalıdır.

Sözlük Oluşturma: Her iki string için ayrı ayrı harf frekansları birer sözlük (dict) içinde saklanır. Python’daki dict.get metodu, eğer bir anahtar mevcut değilse belirtilen varsayılan değeri döndürür, bu örnekte 0.

Karşılaştırma: İki sözlük, Python’da == operatörü ile doğrudan karşılaştırılabilir. Eğer iki sözlük birbirine eşitse, bu iki stringin anagram olduğu anlamına gelir.

Bu çözüm, zaman karmaşıklığı açısından O(n) performans gösterir, çünkü her bir string sadece bir kez taranır ve işlem tamamlandığında her karakterin sayısını içeren sözlükler karşılaştırılır. Alan karmaşıklığı da O(n)‘dir, çünkü en kötü durumda tüm karakterler farklı olabilir ve bu karakterler için hafızada yer ayırılır. Ancak pratikte, sınırlı sayıda karakter (örneğin ASCII veya Unicode) olduğundan, bu değer sabit bir faktöre (örneğin 26 harf için O(1)) indirgenebilir.

    def isAnagram(s, t):
    if len(s) != len(t):
        return False
    
    # Her bir karakterin sayısını tutacak sözlükler
    countS, countT = {}, {}
    
    # İki stringi aynı anda döngü ile geçip karakter sayılarını hesapla
    for charS, charT in zip(s, t):
        countS[charS] = countS.get(charS, 0) + 1
        countT[charT] = countT.get(charT, 0) + 1
    
    # Sözlükleri karşılaştır
    return countS == countT
    

• Zaman Karmaşıklığı (Time Complexity): Bu çözümde her iki string de tam olarak bir kez döngüye girer. Her karakter için hashtable’a erişim ve güncelleme işlemi ortalama O(1) zamanda gerçekleşir. Bu nedenle, bu yaklaşımın toplam zaman karmaşıklığı, iki stringin her biri için yapılan işlemlerin toplamı olan O(n) olur, burada n her iki stringin uzunluğudur. Eğer stringler eşit uzunlukta değilse, işlem daha erken sonlanabilir, ancak en kötü senaryoda bu karmaşıklık geçerlidir.

• Alan Karmaşıklığı (Space Complexity): Hash table’da saklanacak en fazla eleman sayısı, kullanılan karakter setinin boyutuna bağlıdır. Eğer ASCII karakter seti kullanılıyorsa, en fazla 128 veya 256 farklı karakter olabilir (genişletilmiş ASCII seti için). Ancak, pratik uygulamalarda genellikle sadece harfler kullanıldığında bu sayı 26 olabilir (büyük ve küçük harfler ayrı tutulursa 52). Bu durumda, alan karmaşıklığı, kullanılan karakter setine göre O(1) olarak kabul edilebilir, çünkü bu bir sabit boyuttadır ve girdinin uzunluğuna bağlı olarak değişmez. Ancak, girdi boyutuna bağlı olarak düşündüğümüzde, en kötü senaryoda tüm karakterlerin birer kez göründüğü durumda, her bir karakter için bir alan ayırmamız gerektiğinden O(n) olarak ifade edilebilir.