49.group-anagrams.md

49. Group Anagrams

The same gruop of anagrams will have the same count of letters. We can use the count of letters or sort the string as the hash key to group the anagrams.

# Use sorted string as the hash key
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    anagrams = {}
    for str in strs:
        key = ''.join(sorted(str))
        if key not in anagrams:
            anagrams[key] = []
        anagrams[key].append(str)
    return list(anagrams.values())

# Use count of letters as the hash key
def fingerprint(self, s):
    hash_key = ''
    count = [0] * 26
    for c in s:
        count[ord(c) - ord('a')] += 1
    for i in range(26):
        hash_key += str(count[i]) + ','
    return hash_key

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    anagrams = {}
    for str in strs:
        key = self.fingerprint(str)
        if key not in anagrams:
            anagrams[key] = []
        anagrams[key].append(str)
    return list(anagrams.values())

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val group = hashMapOf<String, MutableList<String>>()
    for (str in strs) {
        val countArray = countLetters(str)
        val hash = hashCountLetters(countArray)
        
        if (!group.containsKey(hash)) group[hash] = mutableListOf<String>(str)
        group[hash]!!.add(str)
    }
    return group.values.toList()
}

private fun countLetters(str: String): IntArray {
    val count = IntArray(26)
    for (c in str) {
        count[c - 'a'] += 1
    }
    return count
}

private fun hashCountLetters(countArray: IntArray): String {
    val s = StringBuilder()
    for (i in 0 until count.size) {
        // Suffixing with ',' is necessary which avoids hash collision but different string, see below failed case.
        s.append("${count[i]},")
    }
    return s.toString()
}

• Time Complexity: O(n * k), n is the strs size, k is the length of the longest string.
• Space Complexity: O(n * k) for hash table to store all the strings.

Failed Cases

["ac", "c"]
["ac", "d"]

["bdddddddddd","bbbbbbbbbbc"]
// 0, 1, 0, 10, 0... => 010100
// 0, 10, 1, 0, 0.... => 010100

// Or
// 0, 1, 1, 0, .... => 0110
// 0, 11, 0, 0, ... => 0110