CP #15 : Group Anagrams Problemi

 Problem surada.

Cozum

Naive implementasyonla basliyoruz. Verilen stringleri bir sekilde anagram olup olmadiklarini anlamamiz gerekiyor. Anagram ne demek? Ayni sayida karakter olacak, karakterler de ayni olacak (bu arada soruda karakterler unique olacak diye bir ibare yok) sadece yerleri degisik olacak. Bu bize bir fikir veriyor aslinda. Yani biz verilen stringi, bir array gibi dusunup, alfabetik olarak karakterleri sort edersek, anagramlar ayni sonucu uretecektir. Ornek:

def groupAnagrams(self, strs):

    # her bir stringi karakter bazinda sort ettikten sonra

    # olusan sonucu bu dictionary'de tutacagiz ki

    # ayni ciktiyi veren anagramlari gruplayabilelim

    cache = {}

    for s in strs:

        # stringin karakterlerini sort edip 

        # tekrar bir string olusturuyoruz

        # sort -> O(n logn)

        # string concat -> O(n)

        processed = "".join(sorted(s))

        

        # bu cikti daha once elde edilmis ise

        # bir anagram var demektir. listeye ekleyelim

        if processed in cache:

            cache[processed].append(s)

        else:

            # daha once bu cikti ile karsilasilmadi

            # tek elemani bu string olan bir array ekleyelim

            # ki ileride tekrar ayni cikti ile karsilasirsak

            # kolayca gruplayabilelim

            cache[processed] = [s]

    return cache.values()

Analiz
Bu haliyle gonderdigimde, python gonderileri arasinda %95'inden daha hizli sonuc verdi. Bir kere verilen tum stringileri itere ediyoruz, O(n). Daha sonra her adimda stringin kendisini sort ediyoruz O(k logk) ve string concat islemi yapiyoruz, O(k). Son iki islem, arka arkaya oldugu icin, sortun complexitesi daha yuksek oldugundan loop'un icerisi O(k logk) diyebiliriz. Disaridaki loop da O(n) calistigindan, sonuc olarak O(n k logk) gib bir kompleksiteye sahip oluyoruz. Burada n verilen string sayisi, k ise verilen en uzun string oldugunu hatirlatmakta fayda var. 

Cozumu iyilestirebilir miyiz? 

Analizde gorduk ki, loop icerisindeki sorting kismi baskin. O(k logk). Belki bunu lineer'e cekebilirsek sonuc olarak O(nk) elde edebiliriz. 

Sort etmek yerine, herbir stringde bulunan karakterden kac tane oldugunu sayip, her bir string icin 26 karakter uzunlugunda bir key degeri olusturabiliriz. Buna counting sorting adi verilmektedir. 

from collections import defaultdict

def groupAnagrams(self, strs):

    # biraz daha guzel olsun diye hashtable elemanlarini 

    # bos array olarak init edebiliriz. bu sayede key var mi yok mu 

    # kontrolunden kurtuluyoruz.

    cache = defaultdict(list)

    def count_s(s):

        # herbiri verilen stringdeki harf sayisini 

        # temsil etmek uzere 26 sifirli bir liste olusturuyoruz

        # ornek olarak 2 tane a var ise ret[0] = 2 olacak.

        ret = [0] * 26

        for k in s:

            ret[ord(k) - ord('a')] += 1

        return ret

    for s in strs:

        cache[count_s(s)].append(s)

    return cache.values()

Bu sekilde tekrar inceleyelim. count_s fonksiyonu icerisinde verilen stringin karakter sayisi kadar iterasyon yapiyoruz, O(k). Daha sonra bunu verilen her string icin yapiyoruz, O(nk). 

Tabi kompleksite hersey degil, pratikte bu haliyle leetcode'a submit edince, onceki cozuden daha yavas calisti yaklasik 20 ms kadar. Burada cok fazla faktor olabilir. 

Neyse, stay hungry, stay foolish, stay healthy :)