LeetCode | Backspace String Compare

Herkese selamlar­čĄś­čĆ╝

Bug├╝nk├╝ sorumuz Backspace String Compare. Soru kolay katergorisinde bulunuyor.

Yava┼čtan soruya ge├želim.

Soruyu Anlayal─▒m­čĄö

Soruda bize s ve t ad─▒nda iki tane String de─či┼čkeni veriliyor. Bu de─či┼čkenler # karakteri i├žeriyor ve bu karakterin silme g├Ârevi yani backspace oldu─ču s├Âylenmi┼č. Bizden istenen ise, her bir de─či┼čkende backspace karakterinden ├Ânce hangi karakter var ise, bu karakteri String de─či┼čkenimizden silmemiz.

Soruyu daha net anlay─▒p, kafam─▒zda canland─▒rabilmek i├žin bize sundu─ču ├Ârnekleri inceleyelim.

├ľrnek 1

Input: s = "ab#c", t = "ad#c"

Output: true

A├ž─▒klama: s de─či┼čkeninde # karakterinden ├Ânce 'b' karakterini ve 
          t de─či┼čkeninde # karakterinden ├Ânce gelen 'd' karakterini 
          kald─▒rd─▒─č─▒m─▒zda elimizde iki tane ayn─▒ String ifade olmu┼č
          oluyor, "ac" ve "ac" olarak. Bu y├╝zde True d├Ân├╝yoruz.

├ľrnek 2

Input: s = "ab##", t = "c#d#"

Output: true

A├ž─▒klama: Burda da iki kez kald─▒rma i┼člemi yap─▒yoruz. Ve sonunda
          elimizde iki tane bo┼č String oluyor "" ve "". Bu y├╝zden
          true olarak sonucu d├Ân├╝yoruz.

├ľrnek 3

Input: s = "a#c", t = "b"

Output: false

Explanation: Burada da ayn─▒ i┼člemleri uygulay─▒nca (t de─či┼čkeninde
             backspace yok) elimizde "a" ve "b" kal─▒yor. Dolay─▒s─▒yla
             e┼čit olmad─▒klar─▒ i├žin False d├Ân├╝yoruz.

Soruya Giri┼čelim ­čąŐ

Burada yapmam─▒z gerekenler asl─▒nda basit. Temelde # karakterini g├Ârd├╝─č├╝m├╝z yerde, bir ├Ânceki eleman─▒ de─či┼čkenden silmek. Peki bunu nas─▒l uygulayabiliriz?

Benim ilk akl─▒ma gelen Stack mant─▒─č─▒n─▒ burada kullanmak. Yani mesela elimizde s = "barr#is" de─či┼čkeni oldu─čunu varsayal─▒m ve bir d├Âng├╝ ile bu de─či┼čkenin her bir karakterinde ilerleyelim. E─čer karakter # backspace karakterimize e┼čit de─čilse, o karakteri stack’e ekleyelim. E─čer # backspace karakterine denk gelirsek de, stack’imizden eleman─▒ ├ž─▒karal─▒m.

Burada ben bu stack mant─▒─č─▒n─▒ StringBuilder ile implemente edece─čim. Neden bunu se├žtim? ├ľncelikle elimizdeki de─či┼čken bir String yani asl─▒nda char dizisi. Ve String de─či┼čkenleri immutable de─či┼čkenler oldu─ču i├žin ben her manipule etmeye ├žal─▒┼čt─▒─č─▒mda haf─▒zada yeni bir alan yarat─▒l─▒p, manipule edilen hali orada tutulacak. Yani k─▒sacas─▒ gereksiz haf─▒za kullan─▒m─▒ndan ka├ž─▒nmak istiyorum. (Detay─▒ i├žin bknz. String, StringBuilder, and StringBuffer in Java)

Bir di─čer sebebi de, StringBuilder’─▒n sahip oldu─ču append() ve deleteCharAt() metodlar─▒. append() ile stack gibi en sona ekleme yapabilece─čim, deleteCharAt() metodu ile de istedi─čim yerden, asl─▒nda en sondan, silme i┼člemini (stack’lerde oldu─ču gibi) ger├žekle┼čtirebilece─čim.

┼×imdi bu d├╝┼č├╝nd├╝klerimizi koda d├Âkelim.

   public static boolean backspaceCompare(String s, String t) {
        String sb1 = getFinalString(s);
        String sb2 = getFinalString(t);

        return sb1.equals(sb2);
    }

    // tek tek ayn─▒ ad─▒mlar─▒ yapmak yerine
    // ayr─▒ bir fonksiyon yazd─▒m
    public static String getFinalString(String s) {
      StringBuilder sb = new StringBuilder();

      for (char c : s.toCharArray()) {
        if (c == '#' && sb.length() > 0) sb.deleteCharAt(sb.length()-1);
        else sb.append(c);
       }
      return sb.toString();
    }

Yazd─▒─č─▒m─▒z bu kodu ad─▒m ad─▒m inceleyelim;

  • backspaceCompare() fonksiyonu, iki string parametresi al─▒r: s ve t. ─░lk ├Ânce, her iki string de # karakterinden ├Ânceki karakterleri silerek, geriye kalan karakterleri i├žeren yeni stringler olu┼čturulur. Bunu yapmak i├žin, getFinalString() fonksiyonunu kullan─▒r.

  • getFinalString() fonksiyonu ile # karakterinden ├Ânceki karakterleri silerek sonu├žta geriye kalan karakterleri i├žeren yeni bir string olu┼čturuyoruz.

    • Burada bir StringBuilder nesnesi olu┼čturuyoruz. Bu nesne asl─▒nda bizim stack’imizi temsil edecek ve silme i┼člemlerinden sonra geriye kalan karakterleri tutmak i├žin kullan─▒lacak.

    • Daha sonra, for d├Âng├╝s├╝ kullanarak, fonksiyona g├Ânderilen String de─či┼čkeninin ├╝zerindeki her karakteri tek tek kontrol ediyoruz.

    • D├Âng├╝, her karakteri kontrol edip ‘#’ karakteri ile kar┼č─▒la┼čt─▒─č─▒nda ve StringBuilder nesnesi bo┼č de─čilse, buradaki son karakteri siler (backspace’ten ├Ânceki karakter silindi─či i├žin).

    • Di─čer durumlarda ise, karakter StringBuilder nesnesine eklenir.

    • Son olarak, fonksiyon geri d├Ând├╝r├╝lmeden ├Ânce StringBuilder nesnesi, String’e d├Ân├╝┼čt├╝r├╝l├╝r ve geri d├Ând├╝r├╝l├╝r.

  • Son olarak, fonksiyondan d├Ânen her iki String kar┼č─▒la┼čt─▒r─▒r. E─čer stringler birbirine e┼čitse, true d├Ând├╝r├╝l├╝r, aksi takdirde false d├Ând├╝r├╝l├╝r.

Yazd─▒─č─▒m─▒ bu kodun time complexity‘sinden bahsedecek olursak e─čer, burada olu┼čturdu─čumuz getFinalString() fonksiyonu parametre olarak ald─▒─č─▒ s de─či┼čkeninin t├╝m elemanlar─▒n─▒ ziyaret ediyor. Durum b├Âyle olunca time complexity i├žin O(n) diyebiliriz. Buradaki N asl─▒nda bize input olarak verilen s ve t String’lerinin uzunlu─čudur. Bu nedenle, program─▒n ├žal─▒┼čmas─▒, String’lerin toplam karakter say─▒s─▒na ba─čl─▒ olarak artacakt─▒r.

Tabii ki bu problemin birden farkl─▒ ve daha efektif ├ž├Âz├╝m yollar─▒ olabilir, benim ├ž├Âz├╝m yolum bu ┼čekildeydi ve bunu a├ž─▒klay─▒c─▒ bir ┼čekilde anlatmak istedim.

Buraya kadar zaman ay─▒r─▒p okudu─čunuz i├žin te┼čekk├╝rler,

Happy Coding­čÄë