Learning Journal

2/27/2024

Group Anagrams

function groupAnagrams(strs: string[]): string[][] {
    const hashTB: Record<string, string[]> = {};
   

    for(let i = 0; i < strs.length; i++) {
        const sortedStr = strs[i].split("").sort((a,b) => a.charCodeAt(0) - b.charCodeAt(0)).join("");

        if(hashTB[sortedStr] === undefined)
            hashTB[sortedStr] = [strs[i]];
        else 
            hashTB[sortedStr].push(strs[i]);
    }


    return Object.keys(hashTB).map(key => hashTB[key]);
};


function groupAnagrams(strs: string[]): string[][] {
    const hashTB: Record<string, string[]> = {};
   

    for(let i = 0; i < strs.length; i++) {
        const sortedStr = strs[i].split("").sort((a,b) => a.charCodeAt(0) - b.charCodeAt(0)).join("");

        if(hashTB[sortedStr] === undefined)
            hashTB[sortedStr] = [strs[i]];
        else 
            hashTB[sortedStr].push(strs[i]);
    }


    return Object.keys(hashTB).map(key => hashTB[key]);
};

THE PROBLEM

This problem is fairy simple if you know hash table. The reasoning is as follow. You are asked to return a list of lists of all strings that have the same anagram. The intuition is that you can iterate the array strs, for each string in the array, you drop them to the bucket that contains strings of the same anagram. When finish, you spread out all of the buckets into a list to return. So, you need a data structure that can act as a collection of buckets and each bucket must be labeled according to the anagrams that it is holding. The perfect candidate for that is hash table whose key can be used as label and bucket is an array of string as value.

One more problem is that how can we set the label that is common for all anagrams in a bucket? Well, anagrams are the same when being sorted in alphabet order. So, we can use a sorted anagram as the key.

Revised by ChatGPT

Given an array of strings, the task is to group the strings that are anagrams of each other. Anagrams are words or phrases formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution Overview

The solution involves using a hash table to group strings that are anagrams. The key idea is that all anagrams will have the same string when sorted alphabetically. Therefore, we can use the sorted string as a key in the hash table, and the value will be a list (bucket) containing all strings that are anagrams of each other.

Implementation Details

Create an empty hash table where the key is a sorted string, and the value is a list of strings that are anagrams of the key.
Iterate through the input array of strings. For each string:

Sort the string alphabetically to form the key.
Check if the key is already in the hash table. If not, create a new bucket (list) for this key.
Add the original string to the bucket corresponding to the sorted key.

After processing all strings, the hash table will contain groups of anagrams. Extract these groups and return them as a list of lists.

Complexity Analysis

Time Complexity: O(NKlogK), where N is the number of strings in the input array, and K is the maximum length of a string. Sorting each string takes O(KlogK) time, and we do this for all N strings.
Space Complexity: O(NK), as we need to store all strings in the hash table.