Dizilerde String Eşleşmesi: 1408 Probleminin Çözümü
Merhaba, Fatih Soysal burada. Bu yazıda, programlamada sıkça karşılaşılan bir problem olan “dizilerde string eşleşmesi” konusunu ele alacağız. Özellikle LeetCode’daki 1408 numaralı problem olan “String Matching in an Array” problemini detaylı bir şekilde inceleyeceğiz. Bu problemde, verilen bir dizi içerisinde, kendi alt dizisi olan stringleri bulmamız gerekiyor. Örneğin, [“mass”,”as”,”hero”,”superhero”] dizisi için, “as” stringi “mass” stringinin alt dizisi olduğundan sonuç kümemize eklenecektir. Aynı şekilde “hero” da “superhero” nun alt dizisi olduğu için sonuç kümemize eklenecektir.
Öncelikle problemi daha iyi anlamak için birkaç örnek inceleyelim. Bir dizi düşünün: [“leetcoder”,”leetcode”,”od”,”hamlet”,”code”]. Bu dizide “code” kelimesi “leetcode” ve “leetcoder” kelimelerinin alt dizisi değildir. Dolayısıyla sonuç kümemizde bulunmaz. Ancak “od” kelimesi “leetcode” ve “leetcoder” kelimelerinin alt dizisi olduğu için sonuç kümemizde yer alır.
Problemi çözmek için birkaç farklı yaklaşım mevcut. En basit ve anlaşılır yöntem, brute-force yaklaşımıdır. Bu yöntemde, her bir string için, dizideki diğer tüm stringleri kontrol ederek alt dizi olup olmadığını kontrol ederiz. Bu yöntemin zaman karmaşıklığı O(n^3) olacaktır, burada n dizinin boyutu. Yani, dizi büyüdükçe çalışma süresi oldukça hızlı bir şekilde artacaktır. Bu nedenle, büyük diziler için verimli bir yöntem değildir.
Daha verimli bir yaklaşım ise, KMP (Knuth-Morris-Pratt) algoritmasını kullanmaktır. KMP algoritması, string eşleşme işlemini O(n+m) zaman karmaşıklığında yapar, burada n karşılaştırılan stringin boyutu ve m alt stringin boyutu. Bu yöntem, brute-force yöntemine göre çok daha hızlıdır. Ancak, KMP algoritmasının uygulaması biraz daha karmaşıktır.
Şimdi, JavaScript kullanılarak brute-force yaklaşımının bir örneğini inceleyelim:
function stringMatching(words) {
const result = [];
for (let i = 0; i < words.length; i++) {
for (let j = 0; j < words.length; j++) {
if (i !== j && words[j].includes(words[i])) {
result.push(words[i]);
break; // aynı string bir kere eklenmeli
}
}
}
return result;
}
console.log(stringMatching(["mass","as","hero","superhero"])); // ["as", "hero"]
Bu kod, her bir stringi diğerleri ile karşılaştırarak alt dizi olup olmadığını kontrol eder ve bulduğu alt dizileri sonuç dizisine ekler. Kodun okunabilirliği ve anlaşılırlığı açısından oldukça basittir. Ancak, daha önce de belirttiğim gibi, büyük diziler için verimsiz olabilir. Bu nedenle, büyük veri setleri için daha verimli algoritmalar kullanmak daha mantıklıdır. Daha gelişmiş algoritmalar için bu makaleye göz atabilirsiniz.
Sonuç olarak, dizilerde string eşleşmesi problemi, farklı algoritmalar kullanılarak çözülebilir. Seçilecek algoritma, verilerin boyutuna ve performans gereksinimlerine bağlıdır. Basit ve anlaşılır bir çözüm için brute-force yöntemi kullanılabilir, ancak büyük veri setleri için KMP gibi daha verimli algoritmalar tercih edilmelidir. Kodlamaya devam ederken, daha fazla kaynak ve bilgi için kendi web sitemi ziyaret edebilirsiniz. Başarılar!
#Etiketler: String Eşleşmesi, Diziler, Algoritmalar, JavaScript, Programlama, 1408, LeetCode, KMP Algoritması, Brute-Force, Alt Dizi, String Matching, Veri Yapıları