Teaching Kids Programming – Two Algorithms to Group Anagrams

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Example 2:
Input: strs = [“”]
Output: [[“”]]

Example 3:
Input: strs = [“a”]
Output: [[“a”]]

Constraints:
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Group Anagrams via Sorting and Hash Table aka Dictionary

After sorting, the same group anagram strings will give a same string. We then can use this as a unique key to identify the anagram group. There are N words, and if the maximum word length is K, we need O(KLogK) to sort the words, the overall time complexity is . The space complexity is O(NK) as we use a hash table to store the anagram groups.

1
2
3
4
5
6

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        data = defaultdict(list)
        for s in strs:
            data[tuple(sorted(s))].append(s)
        return data.values()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        data = defaultdict(list)
        for s in strs:
            data[tuple(sorted(s))].append(s)
        return data.values()

We can convert the list (sorted) to tuple and use it as a key. The default dictionary has default value type list.

Group Anagrams via Counting and Hash Table aka Dictionary

Recall that we can use Counter to compare equality of two anagram strings – However, we cannot convert Counter to tuple as it gives incorrect equality test. Given the words are lowercase, we can count and store the frequencies in an array/list.

1
2
3
4
5
6
7
8
9

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        data = defaultdict(list)
        for s in strs:
            d = [0] * 26
            for w in s:
                d[ord(w) - 97] += 1
            data[tuple(d)].append(s)
        return data.values()

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        data = defaultdict(list)
        for s in strs:
            d = [0] * 26
            for w in s:
                d[ord(w) - 97] += 1
            data[tuple(d)].append(s)
        return data.values()

The time complexity is O(NK). so as the space complexity.

See also: Algorithms to Group Words by Anagrams

–EOF (The Ultimate Computing & Technology Blog) —