CP #42: String Problemleri 4
Write A String Sinusoidally
Verilen bir stringi su sekilde sinuzoidal olarak yazdiriyoruz: string: "Hello World!"
e _ l
H l o W r d
l o !
Daha sonra ustten baslayarak sola dogru okudugumuzda sonuc "e_lHloWrdlo!" seklinde olmaktadir. (Alt cizgi boslugu temsil ediyor). Bu gosterime snake-string adini verelim. Verilen bir stringi bu sekilde snake-string haline getiren bir program yaziniz.
Cozum
Benim aklima ilk gelen, uc farkli array tutarak her bir harfi olmasi gerektigi arrayin icine atip, sonda da bunlari birlestirmek. Arraylara da kolay ulasabilmek icin bir dictionary icerisinde level indexi ile ulasilacak sekilde koyabiliriz. Yani H sifir seviyesi, bir yukarisi +1, en asagisi ise -1 olacak.
Bu durumda seviye sifirdan basliyor, yukari gidiyor. +1 oldugu zaman seviye dusmeye basliyor: sirasi ile 0 ve son olarak -1. -1'den itibaren de tekrar yukselmeye basliyor. Bu hareketi, bir baslangic noktasi (sifir) ve de yon (yukari icin +1, asagi icin -1) degiskeni ile saglayabiliriz. Ilk basta seviye sifir yon +1. Daha sonra +1'e ulastigimiz anda yon -1 oluyor ta ki -1'e gidesiye kadar. Sonrasinda tekrar +1'e donuyor.
def snake_string(s):
# seviyesine gore karakterleri tutacak 3 array
# ayni zamanda okuma sirasina gore diziyoruz, +1, 0, -1
chars = { 1: [], 0: [], -1: [] }
level = 0
direction = 1
# verilen stringdeki tum karakterileri dolasiyoruz
for c in s:
chars[level].append(c)
# sinirlara gelince (1 ve -1), yon degisiyor
if level == 1:
direction = -1
elif level == -1:
direction = 1
# gidilen yone bagli olarak leveli guncelliyoruz
level += direction
# dongu icerisinde string concat yapmamak icin array kullaniyoruz
ret = []
# 3 seviyede biriktirdigimiz karakterleri birlestiriyoruz
for k in chars:
ret.append("".join(chars[k]))
return "".join(ret)
Bakacak olursak tum karakterleri traverse ettik ve dongu icerisinde kompleks bir islem yapmadik. Yani lineer bir cozum, O(n), elde etmis olduk. Kullandigimiz hafiza da yine verilen input ile dogru orantili, yani lineer, O(n) space compl. var diyebiliriz.
Implement Run-Length Encoding
Run-length-encoding, cok basit bir metin compression algoritmasidir. Verilen bir string inputtaki karakterleri sayarak, bir kisaltma saglar. Ornegin aaabbb icin 3a3b sonucunu uretir. Yani karakterden kac tane oldugu basta yazili, daha sonra karakterin kendisi. Tek olan karakterler icin de 1 kullanilir. Yani: abbbx icin 1a3b1x sonucu uretilmelidir.
Verilen stringi run-length-encode eden ve de daha sonra tekrar decode eden 2 fonksiyon yaziniz.
Cozum
Once encode ile baslayalim. Buna cok benzer bir problem daha once cozmustuk aslinda, roma rakamini integere cevirirken de karakterin degistigi noktalari tespit etmek gerekiyordu.
Burada yapacagimiz da ayni. Karakterin degistigi yerde, kac tane gectiyse ona gore bir output uretmek.
def rl_encode(s):
# yine loop icerisinde string concat etmemek icin
# array kullaniyoruz
ret = []
# tek karakterli input bizim icin bir edge case teskil ediyor
# cunku stringi itere etmeye 2. karakterden baslayacagiz
# bu sayede daha az if/else kullanmis oluyoruz
if len(s) == 1:
return f"1{s}"
count = 1
for i in range(1, len(s)):
# mecvut karakter bir onceki ile ayni degil
# o zaman bir onceki karakterin sayisini yazdirmamiz
# ve counteri resetlememiz gerekiyor
if s[i-1] != s[i]:
ret.append(str(count) + s[i-1])
count = 1
else:
count += 1
return "".join(ret)
Gayet guzel bir sekilde O(n) time ve space compl. ile encode islemini tamamladik.
Decode islemi de aslinda starightforward:
import string
def rl_decode(s):
digits = set(string.digits)
ret = []
# ilk karakterden baslayarak bir pointe tutacagiz
i = 0
while i < len(s):
# verilen input valid olacagini kabul ederek
# ilk karakter bir rakam olacaktir
# ama ikinci karakter hatta ucuncusu de rakam olabilir
# cunku karakter sayisinda bir sinir yok
# o acidan, rakam olmayan yere kadar gidiyoruz
num_str = ""
while s[i] in digits:
num_str += s[i]
i += 1
# simdi bu noktada tum rakamlari concat ettik
# ve de pointer, karakterin uzerinde suanda (buraya dikakt)
num_val = int(num_str)
ret.append(num_val * s[i])
# sayi belki 1 karakterden fazla olabilir ama
# karakterin kendisi sadece 1 uzunlukta olabilir
# o yuzden direk 1 artirip, siradaki sayiya geciyoruz
i += 1
return "".join(ret)
O(n) time ve space maliyetine sahip bir cozum uretmis olduk.
Substring Search
Verilen bir string ve de hedef kelime icin, kelimenin ilk bulundugu pozisyonu donduren bir program yaziniz. Iyi aciklayamadim biliyorum, ornek;
text = "Hello world" target = "world" , cevap 6 cunku world kelimesi 6. karakterden basliyor.
Cozum
Evet bu enteresan bir soru. Ve de bir interview'de bana sorulmustu. O(n2)'nin altina dusurememistim. Bu yuzden kabul alamadim ama verdigim tum cozum yontemlerini enazindan dogru olarak complexity analizini yapmistim, bu acidan bir sans daha vermek istediler. Neyse, yani time comp. hesabi gercekten cok onemli.
Naive cozum O(n2) ile baslayalim:
def substring_search(text, target):
# target uzerine gezecek olan pointer
tid = 0
# i ise text uzerinde gezecek olan pointer
for i in range(text)
# targetin ilk karakterini bulduk
if text[i] == target[tid]:
# bu buldugumuz noktayi geri dondurecegiz eger hersey yolunda giderse
# yuzden i'yi kaybetmemek icin yeni bir k degiskeni tanimliyoruz
k = i
# targetin veya textin sonunu gecmeden,
# ikisi uzerinde de pointerlari ayni anda hareket ettiriyoruz
# pointerlerin gosterdikleri karakterler ayni oldugu surece devam ediyoruz
while k < len(target) and k < len(text) and text[k] == target[tid]:
k += 1
tid += 1
# eger k degiskeni target kadar ilerleyebilmis ise
# targeti bulduk demektir
# ilk baslangic pozisyonunu dondurebiliriz
if k == len(target):
return i
else:
# eger sona kadar gelemediysek,
# target pointerini sifirlayip text uzerindeki pointeri
# ilerletiyoruz
tid = 0
# bu noktaya geldiysek bulamadik demektir
return -1
En kotu senaryoda, bir ust sinir olarak (text uzunlugu) x (target uzunlugu) kadar donecek bir loop ile problemi cozduk. Bu da O(n2) demektir. Ne mutlu ki ekstra space kullanmadik. Peki time compl. nasil iyilestirebiliriz?
Literaturde substring aramasi icin lineer time compl. sahip 3 algortima var: KMP, Boyer-Moore ve Rabin-Karp. Rabin-Karp bunlardan en basit ve anlasilir olanidir diye bahsedilmekte. (Ben digerlerini arastirmadim).
Rabin-Karp
Aslin bizim yaptigimiz brute-force yaklasima benzer bir yaklasim. Ama, target uzerinde donen 2. donguye ihtiyac duyulmuyor. Bunun yerine finger-print denilen bir yaklasim kullanilmis. Verilen target'in uzunlugu m olsun. Bu algortma, text uzerinde m uzunluktai substringlerin hash'ini hesapliyor. (Bunlara finger-print deniliyor).
Burada efficiency'yi saglayacak esas nokta, incremental hash fonksiyonu kullanmak. Yani bir stringin karakterlerini ekleye ekleye gidebilecek bir hash fonksyionu (Rolling-hash de deniliyor).
Rolling-hash fonksiyonda, elimizde m karakter icin hesaplanmis bir hash varken, bunu 1 karakter saga kaydirdigimizda, pencereden cikan ve pencereye yeni giren degerler ile yeni hash degerini O(1) ile hesaplayabiliyoruz. Avantaj buradan kaynaklaniyor zaten, hashi hesaplamak icin m kere donecek bir loopa gerek kalmiyor.
Burada cok basit bir rolling hash fonksiyonu kullanacagiz. Stringleri 26lik tabanda (cunku 26 ascii standart lowercase karakter var), sayilarmis gibi dusunecegiz. Bu durumda, stringi en soldaki basamagini kaybedip de en sagda yeni bir basamak kazandiginda, pencereyi bir karakter saga kaydirmis oluyoruz.
Ornegin abc icin hash degeri:
base = 26
hash = base**2 * ord("a") + base ** 1 * ord("b") + base ** 0 * ord("c")
seklinde hesaplanir. Bildigimiz 26lik sistemden 10lun sisteme taban donusumu. Daha sonra abc -> bcd seklinde 1 karakterlik kayma oldugunda, yeni hash soyle hesaplanabilir:
hash = 68219 # "abc" hash degeri bu sekilde cikti
new_hash = hash - ord("a") * base ** 1 # once a'nin hash uzerindeki etkisini siliyoruz
new_hash = new_hash * base + ord("d") # yeni gelen d karakterinin etkisini katiyoruz
Ve yeni hash'i bu sekilde O(1) time compl. ile hesaplamis olduk.
import functools
def substring_search(t, s):
# aranacak metin, metnin kendisinden uzunsa bulamayiz
if len(t) < len(s):
return -1
base = 26
# metnin ilk len(s) karakterinin hashini hesaplayalim
t_hash = functools.reduce(lambda hash, char: hash * base + ord(char), t[:len(s)], 0)
# arama metninin hashi
s_hash = functools.reduce(lambda hash, char: hash * base + ord(char), s, 0)
# taban donusumunde kullanacagimiz ilk karakterin etkisi
power_s = base ** max(len(s) - 1, 0)
# ilk len(s) karakteri zaten isledik,
# surekli geriye donuk olarak hash'lari kontrol ederek ilerliyoruz
for i in range(len(s), len(t)):
# hashler esit olacak ama, hash collision olabilir diye stringin kendisini de
# yine kontrol ediyoruz
if s_hash == t_hash and s == t[i - len(s):i]:
return i - len(s)
# len(s) uzunlugundaki penceremizi 1 karakter saga kaydidiyoruz
t_hash -= t[i-len(s)] * power_s
t_hash = t_hash * base + ord(t[i])
# surekli geriye bakarak gittigimiz icin, en son i == len(t) noktasindaki
# karakteri check edemiyoruz bir ustteki loopta
# son olarak onu kontrol edelim
if t_hash == s_hash and s == t[-len(s)]:
return i - len(s)
# buraya kadar geldiysek, bulamadik demektir
return -1
Evet bakacak olursak, t_hash ve s_hash hesaplamalari O(n), ve akabindeki ana loop da yine O(n) maliyete sahip. Toplamda lineer bir substring search cozumu elde ettik ki hic de azimsanacak birsey degil bence. Ekstra space de kullanmadigimiz icin O(1) space compl. de uzerine tatli oluyor.
String konusunu simdilik bu sekilde noktaliyoruz. Ileride tekrar amacli yeni problemler olacak elbet ama simdi plana gore stack/queue problemeri ile bir sonrai postta gorusmek uzere!
Stay hungry, stay foolish and stay healthy :)
Ciao!
Yorumlar
Yorum Gönder