10.02. Group Anagrams

Description

Write a method to sort an array of strings so that all the anagrams are in the same group.

Note: This problem is slightly different from the original one the book.

Example:

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

Output:

[

  ["ate","eat","tea"],

  ["nat","tan"],

  ["bat"]

]

Notes:

All inputs will be in lowercase.
The order of your output does not matter.

Solutions

Solution 1: Hash Table

Thinking

Anagrams share a sorted key. Pairwise anagram tests are \(O(n^2 k)\).

Hashing that sorted string clusters the original words automatically.

For each \(s\), append it to \(d[''.join(sorted(s))]\) and emit the value lists. One \(O(k\log k)\) sort per word buys a hash insert.

Traverse the string array, sort each string according to character lexicographical order, and get a new string.
Use the new string as key and [str] as value, and store them in the hash table (HashMap<String, List<String>>).
When the same key is encountered in subsequent traversals, add it to the corresponding value.

Take strs = ["eat", "tea", "tan", "ate", "nat", "bat"] as an example. At the end of the traversal, the state of the hash table is:

key	value
`"aet"`	`["eat", "tea", "ate"]`
`"ant"`	`["tan", "nat"]`
`"abt"`	`["bat"]`

Finally, return the value list of the hash table.

The time complexity is \(O(n\times k\times \log k)\), where \(n\) and \(k\) are the length of the string array and the maximum length of the string, respectively.

Python3JavaC++GoTypeScriptSwift

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

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> d = new HashMap<>();
        for (String s : strs) {
            char[] t = s.toCharArray();
            Arrays.sort(t);
            String k = String.valueOf(t);
            d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(d.values());
    }
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> d;
        for (auto& s : strs) {
            string k = s;
            sort(k.begin(), k.end());
            d[k].emplace_back(s);
        }
        vector<vector<string>> ans;
        for (auto& [_, v] : d) ans.emplace_back(v);
        return ans;
    }
};

func groupAnagrams(strs []string) (ans [][]string) {
    d := map[string][]string{}
    for _, s := range strs {
        t := []byte(s)
        sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
        k := string(t)
        d[k] = append(d[k], s)
    }
    for _, v := range d {
        ans = append(ans, v)
    }
    return
}

function groupAnagrams(strs: string[]): string[][] {
    const d: Map<string, string[]> = new Map();
    for (const s of strs) {
        const k = s.split('').sort().join('');
        if (!d.has(k)) {
            d.set(k, []);
        }
        d.get(k)!.push(s);
    }
    return Array.from(d.values());
}

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var d = [String: [String]]()
        for s in strs {
            let t = String(s.sorted())
            d[t, default: []].append(s)
        }
        return Array(d.values)
    }
}

Solution 2: Counting

Thinking

With a tiny alphabet the sort key can become a frequency tuple, dropping the \(O(k\log k)\) factor.

A length-\(26\) count (or a tuple built from it) is the key; grouping is unchanged and each word is \(O(k+C)\).

We can also change the sorting part in Solution 1 to counting, that is, use the characters in each string \(s\) and their occurrence times as key, and the string \(s\) as value to store in the hash table.

The time complexity is \(O(n\times (k + C))\). Where \(n\) and \(k\) are the length of the string array and the maximum length of the string, respectively, and \(C\) is the size of the character set. In this problem, \(C = 26\).

Python3JavaC++Go

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

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> d = new HashMap<>();
        for (String s : strs) {
            int[] cnt = new int[26];
            for (int i = 0; i < s.length(); ++i) {
                ++cnt[s.charAt(i) - 'a'];
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > 0) {
                    sb.append((char) ('a' + i)).append(cnt[i]);
                }
            }
            String k = sb.toString();
            d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(d.values());
    }
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> d;
        for (auto& s : strs) {
            int cnt[26] = {0};
            for (auto& c : s) ++cnt[c - 'a'];
            string k;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i]) {
                    k += 'a' + i;
                    k += to_string(cnt[i]);
                }
            }
            d[k].emplace_back(s);
        }
        vector<vector<string>> ans;
        for (auto& [_, v] : d) ans.emplace_back(v);
        return ans;
    }
};

func groupAnagrams(strs []string) (ans [][]string) {
    d := map[[26]int][]string{}
    for _, s := range strs {
        cnt := [26]int{}
        for _, c := range s {
            cnt[c-'a']++
        }
        d[cnt] = append(d[cnt], s)
    }
    for _, v := range d {
        ans = append(ans, v)
    }
    return
}

10.02. Group Anagrams

Description

Solutions

Solution 1: Hash Table

Solution 2: Counting

Comments