LeetCode 49: Anagram Gruplandırma – JavaScript Çözümü

LeetCode 49: Anagram Gruplandırma – JavaScript Çözümü

Bu makalede, LeetCode’un popüler algoritma problemlerinden biri olan “Anagram Gruplandırma” (Group Anagrams) problemine JavaScript dilinde nasıl çözüm getirilebileceğini detaylı olarak ele alacağız. Problem, verilen bir dizi string’i anagram olan gruplar halinde toplamamızı istiyor. Örneğin, [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] girdisi için çıktı [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]] olmalıdır. Öncelikle, anagramın ne olduğunu hatırlayalım. Anagram, harflerinin yer değiştirilmesiyle başka bir kelime oluşturulmasına olanak sağlayan kelimedir. Dolayısıyla, “eat”, “tea” ve “ate” birbirlerinin anagramlarıdır.

Bu problemi çözmek için çeşitli yaklaşımlar kullanılabilir. Ancak, en verimli ve anlaşılır yöntemlerden biri, her bir kelimenin karakterlerinin sıralanmış halini bir anahtar olarak kullanarak bir hash table (JavaScript’te Object) oluşturmaktır. Bu sayede, aynı karakterlere sahip kelimeler aynı anahtara sahip olacak ve aynı gruba ait olacaklardır. İşte adım adım çözüm:

Çözüm Adımları

1. Girdi Dizi İşlemesi: İlk olarak, girdi olarak verilen string dizisini ele alırız.
2. Sıralama ve Anahtar Oluşturma: Her bir string için karakterlerini alfabetik sıraya göre sıralar ve bu sıralı string’i hash table’ın anahtarı olarak kullanırız. Bu anahtar, söz konusu kelimenin anagram grubunu temsil eder.
3. Hash Table’a Ekleme: Sıralanmış string (anahtar), hash table’da mevcut değilse, yeni bir dizi oluşturup bu string’i bu diziye ekleriz. Daha sonra, bu diziyi hash table’da ilgili anahtarın değerine atarız. Eğer anahtar zaten mevcutsa, ilgili diziye orijinal string’i ekleriz.
4. Sonuç Dizi Oluşturma: Hash table’ın tüm değerlerini (yani, anagram gruplarını) bir sonuç dizisine toplarız. Bu sonuç dizisi, istenen çıktı olacaktır.

JavaScript Kodu

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const anagramMap = {};
    for (const str of strs) {
        const sortedStr = str.split('').sort().join('');
        if (!anagramMap[sortedStr]) {
            anagramMap[sortedStr] = [];
        }
        anagramMap[sortedStr].push(str);
    }
    return Object.values(anagramMap);
};

Bu kod, öncelikle boş bir anagramMap nesnesi oluşturur. Daha sonra, girdi dizisindeki her bir string için karakterleri sıralar ve bu sıralı string’i anahtar olarak kullanarak anagramMap’e ekler. Object.values() metodu ile de anagramMap’in değerlerini (yani, anagram gruplarını) içeren bir dizi elde ederiz. Sonuç olarak, verilen string dizisinin anagram gruplarını içeren bir dizi döndürür.

Bu çözümün zaman karmaşıklığı O(NKlogK) ve uzay karmaşıklığı O(NK) ‘dır, burada N string sayısı ve K ortalama string uzunluğudur. Daha verimli çözümler de mevcut olsa da, bu çözümün anlaşılırlığı ve okunabilirliği açısından oldukça iyidir.

Umarım bu makale, LeetCode 49 problemini anlama ve çözme konusunda size yardımcı olmuştur. Daha fazla algoritma ve veri yapısı çözümü için fatihsoysal.com adresini ziyaret edebilirsiniz. Ayrıca, konu ile ilgili daha fazla bilgi için bu bağlantıya göz atabilirsiniz.

#Etiketler: LeetCode, JavaScript, Anagram, Algoritma, Veri Yapısı, Programlama, Çözüm, Gruplama, Hash Table, Anagram Gruplandırma, Group Anagrams