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🎉