CP #17 : Word Break II Problemi
Problem surada.
Cozum
Bir onceki sorunun devami niteliginde ve bu sefer olusturulabilecek tum cumleleri geri dondurmemiz isteniyor. Yine ben aklima ilk gelen yontemle ise baslayacagim. Ne de olsa arkamizdan atli kosturmuyor, maksat cimnastik.
Ben yine backtracking ile baslamak istiyorum. Cunku bu soru icin uygun oldugunu dusunuyorum. String uzerinde kayan bir pencere ile dictionary kontrolu yaparak, bir cozum uretecegiz. Daha sonra bu cozumu baska bir yere kopyaladikta sonra, cozumdeki (veya cozume ulasamamis bir program dalindaki) son kelimeyi cikartacagiz. Ve o kelimeyi almak yerine, onceki kelimeyi bir karakter daha artiracagiz. Bu sayede tum kombinasyonlari denemis olacagiz.
class Solution:
def __init__(self):
# uzerinde calismakta oldugumuz cozumu temsil eden kelimeler
self.cur_solution = []
# bu da bulabildigimiz tum cozumler
self.solutions = []
def solve(self, string, start, dic):
# eger start, sona gelebilmis ise
# bir cozum bulduk demektir
if start == len(string):
self.solutions.append(" ".join(self.cur_solution))
return
end = start + 1
while end <= len(string):
if string[start:end] in dic:
# bu pencere, sozlukte var
self.cur_solution.append(string[start:end])
# bu noktadan itibaren devam et
self.solve(string, end, dic)
# yukaridaki program dali belki cozum uretir
# belki uretmez. uretirse zaten yakalayip
# globaldeki degiskene atiyoruz
# o acidan burada son ekledigimiz kelmeyi
# cikarabiliriz
self.cur_solution.pop()
# pencereyi genisletmeyi unutmayalim
end += 1
def wordBreak(self, s, wordDict):
self.solve(s, 0, set(wordDict)
return self.solutions
Bence gayet guzel bir cozum xD Ancak ne yazik ki bircok testcase pass etse de, yine de timeout olmaktan kurtulamiyor leetcoda'da.
O zaman, dp cozumunu tekrar ziyaret etmek gerekiyor. WordBreak 1'de, dp ile parcalanabilecek noktalari cok performansli olarak tespit etmistik. Bunun uzerine, backtracking ekleyebilir ve olusturulabilecek cumleleri kurabiliriz.
# once wb1'dekinin aynisi sekilde
# split noktalarini bir cache icerisinde tutalim
def wordBreak(self, s, wordDict):
cache = [False] * (len(s) + 1)
cache[0] = True
for end in range(len(s)+1):
for start in range(end):
word_so_far = s[start:end]
left_breakable = cache[start]
if word_so_far in wordDict and left_breakable:
cache[end] = True
break
Simdi cache icerisinde hangi indexten itibaren sola dogru split edilebilir biliyoruz. Yapmamiz gereken split noktalarindan once split edip, bir cozum olusturmak. Daha sonra split etmeden devam ederek baska bir cozum olusturmak. Bu sekilde su ornegi cozebilmis olacagiz:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Once pine noktasindan bolerek geri kalan "applepenapple" icin cozume devam edecegiz.
Bu bittikten sonra pine noktasindan bolmeyerek, bir sonraki bolme noktasindan bolerek, "pineapple" kismini alip "penapple" kismi icin cozume devam edecegiz. Backtracking. Bunun icin solution class'ina global iki degisken ekliyorum:
class Solution:
def __init__(self):
self.solutions = []
self.cur_sol = []
# solve metodu ile de backtraking yaparak
# kurulabilecek cumleleri olusturacagiz
def solve(self, string, start, cache, dic):
# base case, bir cozume ulastik mi?
if start == len(string):
self.solutions.append(" ".join(self.cur_words))
return
# start noktasindan baslayarak
# cache uzerinde iterasyon yapiyoruz
end = start + 1
while end <= len(string):
# eger bu pencereden onceki kisim splittable ve
# bu pencere sozlukte var ise
# gecerli bir cozumdur
if cache[end] and string[start:end] in dic:
self.cur_sol.append(string[start:end])
self.solve(string, end, cache, dic)
# cozumu geri al ve devam et
self.cur_sol.pop()
end += 1
Ayrica bir onceki wordBreak metoduna da ek yaparak, cumleleri olusturma isini bitirelim.
def wordBreak(self, s, wordDict):
# ... bu kisimlar yukaridaki ile ayni
# ... cache olusturuldu
# eger verilen string breakable degilse
# hic cumle olusturmaya calisma
# ben kontrolu atladigim icin bu cozum
# timeout yedi
if not cache[-1]:
return []
# breakable ise, cumleleri olsutur
self.solve(s, 0, cache, set(wordDict))
return self.solutions
Analiz
Bu haliyle leetcode'a gonderidm, python gonderilerinden %70 daha hizli sonuc alabildim. Wordbreak kisminda, yani cache olusturdugumuz kisimda zaten O(n2) kompleksite var. Iki tane dongu icerisinde cahe'i olsuturuyoruz. Backtracking ise biraz daha karmasik gozukuyor. Worst case'i dusunerek bir cikarim yapmak gerekecek. Bu kismi henuz dogrulayamadim, ama bana dogru gibi geliyor.
Ornek olarak elimizde soyle bir input olsun:
s= "123"
wordDict = ["1", "2", "3", "12", "23", "123"]
solution = ["1 2 3", "1 23", "12 3", "123"]
Yani aslinda harflerin tum sirali kombinasyonu demek oluyor. 3 harfli inputa karsilik, 4 cozum urettik. Guvenli tarafta olabilmek adina bence burayi O(2^n) kabul edebiliriz.
Bu tabi backtrack yapan solve metodunun calistirilma kompleksitesi. Bir de solve metodunun kendi kompleksitesi var. Onda da, start -> end arasinda verilen input stringi itere ediyoruz. Worst-case olarak onu da O(n) sayabiliriz. Bu durumda cache olusturulduktan sonra, cumle olusturma kismi O(n 2^n) seklinde oluyor. Bu da bir onceki adimdan gelen O(n^2)'yi bastiracaktir. Ve sonuc olarak cozumumuz O(n 2^n) seklinde oluyor.
Diger bir problemde gorusmek uzere. Stay hungry, stary foolish, stay heathy :)
Yorumlar
Yorum Gönder