Leetcode 49 Group Anagrams

Leetcode 49 Group Anagrams

Group Anagrams – LeetCode

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

The key for this problem is how to check if two words are anagrams. One good way is to encode the word in a way that anagrams have the same encoding.

The way we are encoding is to calculate the number of appearances for each letter for all 26 letters. But we would use an array of length of 26 to represent each letter for each index. So we would need to convert each letter to a index between 0 and 25 by calculating the distance between the letter and letter a in char code. e.g

• abc -> ‘1,1,1,0,0,0,0,0,0,0,0…..0’
• bbdf -> ‘0,2,0,1,0,1,0,0,0,0,0,0,0…..0’

Solution

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    
    const encode = (s) => {
        let array = new Array(26).fill(0)
        for(let i = 0; i < s.length; i++) {
            let index = s.charCodeAt(i) - "a".charCodeAt(0)
            array[index]++;
        }
        return array.join(',');
    }

    let map = {};
    for(let i = 0; i < strs.length; i++) {
        let key = encode(strs[i]);
        if(!map[key]) {
            map[key] = [strs[i]]
        } else {
            map[key].push(strs[i])
        }
    }

    return Object.values(map).reduce((acc, v) => {
        acc.push(v);
        return acc;
    }, []);
};

Time Complexity:
O(nm) where n is the length of each word and m is the length of the array

Space Complexity:
O(nm) where n is the length of each word and m is the length of the array