CP #40: String Problemleri 2

Spreadsheet Column Encoding

Excel gibi spreadsheet uygulamalarinda, stunlar icin bir isimlendirme formati vardir. A, B, C ... X, Y, Z, AA, AB, AC ... ZZ, AAA, AAB ... seklinde devam eder. 

Verilen bir stun basligi icin, index degerini hesaplayaniz. 

Ornek: D -> 4, AA -> 27,  ZZ -> 702. 

Bu kodu nasil test edersiniz?

Cozum

Aslinda yine bir taban donusumu. A gordugumuz zaman 1'i temsil ediyor, ve verilen string, 26lik tabanda yazilmis (26 ascii standart karakter var toplamda). 

AA -> 26 * 1 + 1 = 27 seklinde donusturulebilir. 

import string

def col_to_index(col):

    ret = 0

    # A'dan Z'ye kadar olan uppercase ascii karakterleri

    tbl = string.ascii_uppercase

    for c in col:

        # basamak degerine bir ekliyoruz cunku 

        # tbl.index("A") sifir  dondurecektir, bize 1 lazim

        ret = ret * len(tbl) + (tbl.index(c) + 1)

    return ret

O(n) time compl. ve ekstra space kullanmadik, O(1) space compl. Test etmek icin de, karakter sayisinin degistigi noktalar mantikli duruyor. Yani A, AA, AAA noktalarini test etmek gerekir. 

Follow up:

Peki verilen bir indexi, stun basligina nasil cevirebiliriz? Ornek : 4 -> D, 27 -> AA, 702 -> ZZ

Cozum

Bu biraz daha tricky. Evet verilen string, 26'lik tabanda cunku bir basamak 26 farkli deger alabiliyor (A'dan Z'ye kadar). Ancak A'nin 1'e tekabul etmesi isleri zorlastiriyor. Bu acidan ya character mappingi degistirecegiz, yani yeni bir lookup uretip, 1->A haline getirecegiz ya da, ben sayi 27lik tabandaymis gibi dusunebiliriz. 

def index_to_col(id):

    tbl = string.ascii_uppercase

    ret = []

    while id:

        cur = id % 27

        ret.append(tbl[cur-1])

        id //= 27

    return "".join(reversed(ret))

Seklinde verilen 10luk tabandaki sayiyi 27 tabaninda bir sayiya donusturmus oluyoruz. O(n) time ve O(n) space compl. sahibiz. 

Test Palindromicity

Verilen string, alphanumerik karakterler haricinde palindromik mi degil mi kontrol ediniz.
Yani "Ey edip! Adana'da pide ye!" , palindromiktir ve True dondurmek gerekir. 

Cozum

Naive implementasyonda, verilen stringi reverse etmek, non-alpha numerik karakterleri (yani a'dan z'ye kadar olan karakterlerden olmayan, noktalama gibi, bosluk gibi karakterler) filtreleyerek karsilastirabiliriz. Ancak bu ekstra space gerektirir. Buna gerek yok, Two pointers yontemini kullanabiliriz. 

def is_pal(s):

    # en basta ve ensonda birer pointer tutuyoruz

    # alphanumerik oluncaya kadar bu pointerleri soldakini ileriye,

    # sagdakini de geriye dogru kaydiriyoruz ve karakterleri karsilastiriyoruz

    # egere farkli iseler direk False dondurebiliriz

    

    x = 0

    y = len(s) - 1

    

    while y > x:

        # alpha-numerik bir karakter bulana kadar devam et

        while not s[x].isalnum():

            x += 1

        while not s[y].isalnum():

            y -= 1

        # suanda s[x] ve s[y] de alpha numerik

        if s[x] != s[y]:

            return False

        else:

            x += 1

            y -= 1

    

    # buraya kadar gelebildiysek palindrome var demektir

    return True

Ekstra space kullanmadan O(1) ve de lineer bir time compl. O(n), problemi cozmus olduk.

Reverse All The Words In A Sentence

Verilen bir cumledeki tum kelimeleri reverse ediniz. Cumle bir array ve her bir karakter bir string olarak tutuluyor. 

Ornek "lombak sizi seviyor" -> "seviyor sizi lombak".

Burada aslinda input ["l", "o", "m", "b", "a", "k", ... ] seklinde !

Cozum

Ekstra space kullanarak cozmek cok trivial. Verilen arrayi okuruz, bosluk geldiginde, o ana kadar okuduklarimizi bir yerde tutuariz. Tuma array okumasi bittikten sonra da, kaydettigimiz bu kelimeleri reversed olarak birlestirirz. Bu durumda O(n) space kullanmis oluruz.

Ama esas problem O(1) space ile cozumde. Bunun icin tum islemleri inplace olarak array uzerinde yapmak gerekiyor. 

Ilk akla gelen sey, tum arrayi direk reverse etsek nasil olur?

lombak sizi seviyor --> royives izis kabmol 

Aslinda fena degil. Tek problem, herbir kelimenin reversed olarak ortaya cikmis olmasi. Ikinci pass'te de bunlari duzeltirsek, bizden iyisi yok valla :D

def reverse_words(s):

    # once tum cumleyi daha sonra da tek tek kelimeleri reverse 

    # edecegimiz icin, belirli bir range uzerinde reverse islemi yapan

    # bir fonk tanimliyoruz

    def reverse_range(s, start, finish):

        while finish > start:

            s[start], s[finish] = s[finish], s[start]

            start += 1

            finish -= 1

    #once tum cumleyi reverse ediyoruz

    reverse_range(s, 0, len(s) - 1)

    # simdi kelimeleri tek tek inplace olarak reverse ediyoruz

    # her bir kelime icin start ve finish seklinde 2 pointer tutalim

    finish = 0

    while True:

        start = finish

        # finish pointeri, bosluga gelene kadar ilerletiyoruz

        while s[finish] != " ":

            # pointeri ilerletirken cumlenin disina cikiyorsak

            # reverse islemi bitmis demektir, return edebiliriz

            if finish = len(s) - 1:

                return

            finish += 1

        

        # bu noktada elimizde bir kelimenin baslangic ve bitis

        # indexleri var, inplace reverse edelim

        # boslugu almamak icin, finish'ten 1 cikardik

        reverse_inplace(s, start, finish - 1)

        # boslugu atlamak icin, finish degerini 1 artiyiroruz

        finish += 1

        # burada dongu basa donecek ve bu sefer baslama noktasi

        # burada bitirdigimiz yer olacak yani finish pointeri.

Evet bakacak olursak hic ekstra space kullanmadik, tamaaam O(1) !

Ve de sadece ileri yonde tek bir iterasyon ile kelimeleri reverse ettik, O(n) time compl. ile problemi sonlandiriyoruz. 

Neler Ogrendik?

• s[~i] ile sondan sifir bazli karakter getirme:
  for loop icerisinde bir stringin basindan ve sonundan
  ortaya dogru gelmek icin kullanilabilir. ~0, ensondaki karakteri temsil ediyor. 
  
  for i in range(len(s)//2):
      s[i], s[~i] = s[~i], s[i]

• int -> char donusumu
  chr(ord("0") + 5) ==> "5" 

• char -> int donusumu:
  import string
  string.digits.index("5") ==> 5
  
  
• Karakter seti alma
  string.ascii_lowercase
  string.ascii_uppercase
  
  
• Karakter alfanumerik mi?
  string[i].isalnum() == True 

Diger problemlerde gorusme uzere. Hayirli hackler!