CP #39: String Problemleri 1
String de aslinda elemanlari character olan bir arraydir. Ancak kendine has operasyonlar barindirdigi icin ayri degerlendirilmektedir. Immutable bir yapida olup, sadece tek bir karakter set edilemez. Ayrica string uzerinde yapilan operasyonlar sonucu yeni string uretili, varolan degistirilmez. Yani "lombak" + "sehidi" gibi en basit string concat islemi O(n) zaman almaktadir.
String ile alakali soylenecek cok baska birsey yok. Orneklere gecelim:
Palindrom mu?
Cok basit bir ornek ile python sov yapalim: Verilen stringing palindrom mu oldugunu bulalim.
def is_palindrome(s: str) -> bool:
# buradaki ~i indexi, arrayin sonundan sifir bazli index ile eleman almaya yariyor.
# yani ~0 en sondaki elemani getirir
# yani ~0 en sondaki elemani getirir
return all(s[i] == s[~i] in for i in range(len(s) // 2)]
Time O(n), space O(1) seklinde bir cozum.
String Donusturme
Bir int represent eden stringi, int'e donusturunuz. Ayni sekilde verilen bir int'i de stringe donusturunuz. Tabi ki python hazir fonk. kullanmadan. Ayrica pozitif ve negatif sayilari, eksi ve artiyi da dikkate alarak.
Cozum
Once int -> str donusumunu yapalim. Mevcut python fonk. kullanamayacagimiza gore, her bir basamakta hangi sayi var bunu bulmamiz gerekiyor. Modulus (kalan) operatoru ile bunu yapabiliriz.
def int_to_str(n: int) -> str:
# python fonk kullanmayacagimiz icin, sayidan stringe cevirmeyi de kendimiz yapacagiz.
# bu durumda bir lookup table isimize yaracaktir.
tbl = {
0: "0", 1: "1", 2: "2", 3: "3", 4: "4", 5: "5",
6: "6", 7: "7", 8: "8", 9: "9"
}
ret = ""
# isareti bastan kontrol edelim
sgn = n > 0
# sayi negatif ise modulo operatoru bekledigimizden farkli sonuc verecektir
n = abs(n)
while n:
# mevcut ensondaki basamagi aldik
res = n % 10
# lookup tabledan bu sayi icin hangi karakter gerekli ona bakalaim
ret = tbl[res] + ret
# int division ile sayinin son basamagini atiyoruz
# bu sayede diger basamaga gecmis oluyoruz
# yani 457 ise, 45 haline geliyor
n = n // 10
# isareti de ekleyelim
if not sgn:
ret = "-" + ret
return ret
Bakacak olursak, while loop icerisinde bir string concat islemi var yani O(n). Bizi toplamda O(n2) cozume getiriyor. Basamaklari bir array icerisinde toplayarak, en sonda concat edebilir ve O(n)'e dusurebiliriz. Space de yine O(n) olarak gozukuyor.
Biraz arastirma yapinca birkac trick'e rastladim. Onlari paylasmak istiyorum. Biz burada sayilar icin intten stringe cevirirken bir lookup table kullandik ama karakter donusumu ile de bunu yapabiliriz. Ornegin sifirin karakter kodunu alip, buna stringe donusturmek istedigimiz rakami ekler ve karaktere donusturursek, yani:
chr(ord("0") + 5) ==> "5" sonucu elde etmis oluruz.
Aslinda mantikli, cunku karakter tablosunda 0'dan 9'a kadar olan sayilar sirayla ilerliyor ve aralarinda 1'er karakter kodu fark var. Bahsettigimiz optimizasyon ile kodu tekrar guncellersek:
def int_to_str(n):
sgn = n > 0
n = abs(n)
ret = []
while n:
cur = chr(ord("0") + n % 10)
ret.append(cur)
n //= 10
if not sgn:
ret.append("-")
return "".join(reversed(ret))
String'den int'e cevirme icin:
def str_to_int(s: str) -> int:
# bu sefer de char'dan rakama bir lookup table gerekli
tbl = {
"0":0, "1": 1, "2":2, "3":3, "4":4, "5":5,
"6":6, "7":7, "8":8, "9": 9
}
# basinda eksi isareti var mi?
sgn = 1
if s[0] == "-":
sgn = -1
s = s[1:]
ret = 0
mul = 1
# en sagdaki digitten baslayarak,
# toplayarak ilerliyoruz
# toplayarak ilerliyoruz
for i in range(len(s) - 1, -1, -1):
ret += mul * tbl[s[i]]
# her adimda basamak degerini 10 ile carpiyoruz
mul *= 10
return ret * sgn
Seklinde bir cozum elde ettik. Sadece bir adet for loop var, toplamda O(n) time compl. sahibiz. Ekstra space tutmadigimiz icin de O(1) space compl. var diyebiliriz.
Lookup table kullanmak yerine de python'un string kutuphanesinde yeralan digit degerini kullanabilirmisiz. Stringe cevirmek istedigimiz rakami index olarak kullanarak, rakamin string degerini elde edebiliyormusuz. Ogrenmenin yeri, zamani ve yasi yok arkadaslar. Okul, sadece etrafi dort duvarla kapli ve tuvaletinde sigara icilen yerler degildir!
import string
string.digits.index("5") ==> 5
string.digits.index("5") ==> 5
Base Conversion
b1 tabaninda bir integeri represent eden bir string veriliyor. Bunu b2 tabanina donusturunuz.
Ornek: ("615", 7, 13) yani 7 tabaninda verilen 615 sayisini 13 tabanina donusturunuz. Sonuc: 1A7
10 icin A, 11 icin B ... 15 icin de F kullanilacaktir.
Cozum
Verilen stringi once bir ara tabana cevirip, daha sonra o tabandaki integeri istenen base'e cevirebiliriz.
Verilen stringi once bir ara tabana cevirip, daha sonra o tabandaki integeri istenen base'e cevirebiliriz.
def base_conv(s, b1, b2):
# verilen stringi 10 luk tabanda bir integere cevirelim
# bu sefer soldan baslayarak saga dogru gidiyoruz ve her adimda
# onceki sayi degerini 10 ile carpip mevcut basamak degerini ekliyoruz
# en sagdan da baslayabilirdik ama bu yontem daha elegant duruyor
base10 = 0
for c in s:
base10 = base10 * b1 + string.digits.index(c)
# simdi de istenen b2 tabanina cevirecegiz
# soruda da verildigi uzere taban 10'dan buyuk olursa
# rakam olarak A,B,C ... kullanmak gerek
# bunun icin bir lookup table yapalim
tbl = {
10: "A", 11: "B", 12: "C", 13:"D", 14:"E", 5:"F"
}
ret = []
while base10:
# en sagdaki basamak
cur = base10 % b2
# basamak 9'dan buyukse lookup table'dan bakmamiz gerek
if cur > 9:
ret.append(tbl[cur])
else:
# bir onceki soruda ogrendigimiz trick ile
# basamak degerini stringe cevirelim
ret.append(chr(ord("0") + cur)
base10 //= b2
# arraye surekli sondan ekleme yaptigimiz icin
# cevap ters sekilde olustu. reverse ederek duzeltiyoruz
return "".join(reversed(ret))
Aslinda strightforward bir cozumu var diyebiliriz. Iki adet loopumuz var ama iclerinde kompleks bir islem yok, dolayisi ile O(n) bir cozum. Ve basamak degerlerini ekstra olarak arrayda tuttugumuz icin O(n) space comp. sahip.
Simdilik bu kadar, diger problemlerde gorusmek uzere,
stay hungry, stay foolish, stay healthy :)
Yorumlar
Yorum Gönder