LeetCode 30: Tüm Kelimelerin Birleşimiyle Alt Dize – JavaScript Çözümü

LeetCode 30: Tüm Kelimelerin Birleşimiyle Alt Dize – JavaScript Çözümü

Bu makalede, LeetCode’un 30. problem olan “Tüm Kelimelerin Birleşimiyle Alt Dize” problemini ele alacağız. Bu problem, verilen bir metin dizesi içinde, belirli bir kelime dizisinin tüm kelimelerini içeren ardışık bir alt dize bulmayı gerektirir. Öncelikle problemi daha iyi anlamak için bir örnek inceleyelim. Sonrasında ise, JavaScript kullanarak yüksek performanslı bir çözüm geliştireceğiz. Ayrıca, kodun işleyişini adım adım açıklayarak, karmaşıklığı azaltmayı hedefleyeceğiz.

Problem Tanımı

Problem şu şekilde özetlenebilir: Verilen bir s metin dizesi ve bir words kelime dizisi vardır. words dizisindeki tüm kelimelerin, s dizesinde, ardışık ve aynı sırayla yer alan bir alt dize olup olmadığını bulmamız gerekiyor. Örneğin, s = "barfoothefoobarman" ve words = ["foo","bar"] ise, çıktı [0,9] olmalıdır, çünkü “foobar” ve “barfoo” alt dizeleri s dizesinde yer almaktadır.

Çözüm Yöntemi

Bu problemi çözmek için, slayt pencere tekniğini (sliding window) kullanacağız. Bu teknik, belirli bir pencere boyutunda dizi üzerinde yineleme yaparak, performansı artırmamızı sağlar. Öncelikle, her kelimenin uzunluğunu belirleyeceğiz. Ardından, slayt penceresi ile s dizesi üzerinde yineleme yapacağız. Her yinelemede, pencere içindeki alt dizeyi, words dizisiyle karşılaştıracağız. Eşleşme durumunda, alt dizeyi içeren indeksi döndüreceğiz. Böylece, tüm kelimelerin birleşimini içeren alt dizelerin başlangıç indekslerini bulabiliriz. Bu yaklaşım, brute-force yöntemine göre çok daha verimli olacaktır.

JavaScript Kodu

function findSubstring(s, words) {
  const wordLength = words[0].length;
  const totalLength = wordLength * words.length;
  const result = [];
  const wordCount = {};

  for (const word of words) {
    wordCount[word] = (wordCount[word] || 0) + 1;
  }

  for (let i = 0; i <= s.length - totalLength; i++) {
    const window = {};
    let j = 0;
    while (j < words.length) {
      const word = s.substring(i + j * wordLength, i + (j + 1) * wordLength);
      if (!wordCount[word] || window[word] === wordCount[word]) {
        break;
      }
      window[word] = (window[word] || 0) + 1;
      j++;
    }
    if (j === words.length) {
      result.push(i);
    }
  }
  return result;
}

Kod Açıklaması

Kod, öncelikle her kelimenin uzunluğunu ve toplam uzunluğu hesaplar. Sonra, words dizisindeki kelimeleri ve sayılarını bir nesnede depolar. Döngü içerisinde, slayt pencere tekniği ile s dizesi üzerinde yineleme yapar. Her yinelemede, pencere içindeki alt dizeyi, words dizisiyle karşılaştırır. Eşleşme durumunda, alt dizeyi içeren indeksi result dizisine ekler. Son olarak, result dizisini döndürür.

Performans Analizi

Bu çözümün zaman karmaşıklığı O(n*m) , burada n, s dizesinin uzunluğu ve m, words dizisinin uzunluğudur. Bu, brute-force yöntemine göre çok daha verimlidir. Bellek karmaşıklığı ise O(m) düzeyindedir, çünkü words dizisini bir nesneye kaydediyoruz. Genel olarak, bu çözüm, LeetCode'un 30. problemine etkili bir çözümdür.

Sonuç

Bu makalede, LeetCode'un 30. problem olan "Tüm Kelimelerin Birleşimiyle Alt Dize" problemini JavaScript kullanarak çözümledik. Slayt pencere tekniği ile yüksek performanslı bir algoritma geliştirdik. Umarım bu makale, bu zorlu problemi anlamanıza ve çözmenize yardımcı olmuştur. Daha fazla algoritma ve problem çözümü içeriği için fatihsoysal.com adresini ziyaret edebilirsiniz. Ayrıca, konu ile ilgili daha fazla bilgi için burayı inceleyebilirsiniz.

#Etiketler: LeetCode, JavaScript, Algoritma, Programlama, Çözüm, Alt Dize, Substring, Kelime Birleştirme, Problem Çözme, Sliding Window, FatihSoysal