49. Group Anagrams

Problem

https://leetcode.com/problems/anagrams/

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],

Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

Solution

sort the letters in each word

Solution One

sort function

 /**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let groups = {}

    strs.forEach(word => {
        let index = word.split('').sort().join('')
        if (groups[index] !== undefined) {
            groups[index].push(word)
        } else {
            groups[index] = [word]
        }
    })

    let result = []
    Object.keys(groups).forEach(key => {
        result.push(groups[key])
    })

    return result
};

Solution Two

Since all inputs are in lower-case, use counting sort will significantly improve performance.

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    if (strs.length <= 0) { return [] }

    let groups = {}

    let alphabetTemplate = []
    for (let i = 0; i < 26; i += 1) {
        alphabetTemplate[i] = 0
    }

    strs.forEach(word => {
        let alphabet = alphabetTemplate.slice()
        for (let i = 0; i < word.length; i += 1) {
            alphabet[word.charCodeAt(i)-97] += 1
        }

        let index = String.fromCharCode.apply(null, alphabet)
        if (groups[index] !== undefined) {
            groups[index].push(word)
        } else {
            groups[index] = [word]
        }
    })

    let result = []
    Object.keys(groups).forEach(key => {
        result.push(groups[key])
    })

    return result
};