CP #16: Word Break Problemi

 Problem surada.

Cozum

Naive implementasyon ile baslayalim. 

Two pointer approach kullanacagiz. Start ve end degiskenleri mevcut pencereyi temsil edecek. Eger mevcut pencere, dict icerisinde var ise, start'i end'e getirip, end'i bir artiracagiz ve devam edecegiz. Buraya kadar greedy bir algoritma cunku egere sozlukte varsa direk onu aliyor. Ama belki de onu direk almamasi gerekir. Ornek:

verilen input: aaaaa, sozluk: aa, aaa 

simdi bunun True dondurmesi gerekiyor cunku "aaa" + "aa" seklinde ayirabiliriz. Ama suana kadarki olusturdugumuz yontemle gidersek, surekli "aa" da devam edecegiz ve sonra tek bir "a" kalacak. Bu durumda string parse edilemez karari verecegiz. 

Bu da aslinda backtracking anlamina geliyor. Yani son olarak sozlukten aldigimiz "aa" degeri ile cozume ulasamadi isek, bunu birakip kaldigimiz yerden yolumuza devam etmemiz gerekir. Bu durumda "aaa" cozumune de erisebilir ve dogru sonucu hesaplayabiliriz. 

class Solution:

    def __init__(self):

        # sonuca ulasmamiz icin programin bir yerinde dallanmasi gerekiyor

        # boyle olunca da sonuca ulasip ulasamadigimizi anlamak zorlasabilir

        # kolay bir yontem global bir degiskende bunu tutmak

        self.ret = False

        # sonuca goturen kelimeler

        self.words = []

    def solve(self, string, start, dic):

        # verilen stringin sonuna kadar gelebildiysek

        # parse edebilmisiz demektir.

        if start == len(string):

            self.ret = True

            return True

        # start noktasindan baslayarak bir window olsuturuyoruz

        end = start + 1

        while end <= len(string):

            # eger window dictionary icinde var ise

            if string[start:end] in dic:

                # kelimeyi al

                self.words.append(string[start:end)

                

                # windowun bittigi noktadan cozmeye devam et

                # burada program dallaniyor, eger aldigimiz bu kelime

                # bizi sonuca ulastirir ise bir noktada self.ret degeri True

                # olarak atanacak. 

                # egere basarili olamazsa, bu deger False olarak kalacak

                self.solve(string, end, dic)

                # basarili olamadik

                if not self.ret:

                    # o zaman son eklenen kelmeyi cikart 

                    self.words.pop()

            

            # windowun bitis noktasini ilerlet

            end += 1

    def wordBreak(self, s, wordDict):

        self.solve(s, 0, set(wordDict))

        return self.ret

Analiz

Malesef bu cozum verilen ornek inputlar icin calissa da, gercek test-case'lere gelince timeout oluyor. Zaman kompleksitesini de suan tam olarak analiz edemedim. Benzer bir backtracking icin O(n^n) denilmis internette ama onu da tam analayabilmis degilim. Neyse, sonucta daha performansli olan cozum DP tarafindan geliyormus. Simdi ona bir gozatalim. 

Mevcut cozumun uzun surmesinin sebeplerine bakarsak, surekli basa donuyoruz ve tekrar hesaplama yapiyoruz. Bunun onune gecebilmek icin bir cache kullanabiliriz. Zaten dynamic programming'in olayi da bu degil mi? 

verilen string uzunlugundan bir fazla eleman icerecek sekilde bir cache olusturmamiz gerekiyor. Buradaki her bir eleman da string icerisindeki i. elemana kadar olan kismin soruda istenen sekilde split edilip edilemeyecegini belirtecek. Bu sayede ornegin 5. karaktere kadar olan kismin split edilip edilemeyecegini biliyor olacagiz ve tekrar hesaplama yapmayacagiz. Ilk deger True olmali cunku stringin en basinda, bos karakter her zaman icin split edilebilir. 

def wordBreak(self, s, wordDict):

    cache = [False] * (len(s) + 1)

    cache[0] = True

    # python'da range operasyonu, yani s[start:end], bitis indisi exlusive oldugu icin

    # string uzunlugunun bir fazlasina kadar gidiyoruz.

    for end in range(len(s)+1):

        for start in range(end):

            # mevcut window icerisindeki kelime

            word_so_far = s[start:end]

            

            # baslangic noktasindan oncesi, 

            # yani sol taraf, split edilebilir mi?

            left_splittable = cache[start]

            

            # eger mevcut window icerisindeki kelime   

            # sozlukte varsa ve de baslangic noktasindan oncesi de

            # split edilebiliyorsa, bir cozum bulduk demektir        

            if left_splittable and word_so_far in wordDict:

                cache[end] = True

                break

    # cache'teki son eleman, kendisinden once gelen

    # kismin tamaminin splittable olup olmadigini

    # gosterdigi icin, buna bakarak tum kelimenin 

    # split edilip edilemeyecegini anlayabiliriz

    return cache[-1]

Bu gercekten de performansli bir cozum ve 28ms gibi bir sure ile python gonderilerinin %98'inden daha hizli sonuc veriyor. Kompleksiteye bakacak olursak da, dis dongude 0'dan string sonuna kadar gidiyoruz. Ic dongude de yine sifirdan, dis dongu pozisyonuna kadar donuyoruz. Toplamda O(n2) seklinde bir kompleksiteye sahip. Hafiza gereksinimi ise, ekstra bir cache tuttugumuz icin O(n) olmaktadir. 

Trivial bir soru degildi, tam net olarak anlamanin onemli oldugu problemlerden bir tanesi diye dusunuyorum. Diger bir problemde gorusene kadar stay hungry, stay foolish, stay healthy :)