49. Group Anagrams

Description

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

Example 1:

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

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

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

1 <= strs.length <= 10⁴
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Solutions

Solution 1: Hash Table

Thinking

The first idea is pairwise anagram checks: sort each string and compare. Correct, but \(n \le 10^4\) and \(k \le 100\) make \(O(n^2 \cdot k \log k)\) too slow.

Pairwise comparison is the bottleneck. Anagrams share one sorted form — that string is the group id.

Use the sorted string as key and a list of originals as value. One pass into a hash table clusters them; no pairwise matching.

Traverse the string array, sort each string in character dictionary order to 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 encountering the same key during subsequent traversal, 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 lengths of the string array and the maximum length of the string, respectively.

Python3JavaC++GoTypeScriptRustC#

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());
}

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut d = HashMap::new();
        for s in strs {
            let mut t: Vec<char> = s.chars().collect();
            t.sort_unstable();
            let k: String = t.into_iter().collect();
            d.entry(k).or_insert_with(Vec::new).push(s);
        }
        d.into_values().collect()
    }
}

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var d = new Dictionary<string, List<string>>();
        foreach (string s in strs) {
            char[] t = s.ToCharArray();
            Array.Sort(t);
            string k = new string(t);
            if (!d.ContainsKey(k)) {
                d[k] = new List<string>();
            }
            d[k].Add(s);
        }
        return new List<IList<string>>(d.Values);
    }
}

Solution 2: Counting

Thinking

Solution 1 sorts every string, \(O(k \log k)\) each. The alphabet is \(26\) lowercase letters; with \(k \le 100\) the \(\log k\) factor is waste.

What it lacks is a cheaper key. Count each letter and use the length-\(26\) tuple as the key. Same hash grouping, linear per string.

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 use 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 lengths 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++GoTypeScriptRustC#

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
}

function groupAnagrams(strs: string[]): string[][] {
    const d = new Map<string, string[]>();
    for (const s of strs) {
        const cnt = new Array(26).fill(0);
        for (const c of s) {
            cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        const key = cnt.join(',');
        if (!d.has(key)) {
            d.set(key, []);
        }
        d.get(key)!.push(s);
    }
    return Array.from(d.values());
}

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut d = HashMap::new();
        for s in strs {
            let mut cnt = [0; 26];
            for c in s.chars() {
                cnt[(c as usize) - ('a' as usize)] += 1;
            }
            d.entry(cnt).or_insert_with(Vec::new).push(s);
        }
        d.into_values().collect()
    }
}

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var d = new Dictionary<string, List<string>>();
        foreach (string s in strs) {
            int[] cnt = new int[26];
            foreach (char c in s) {
                cnt[c - 'a']++;
            }
            string key = string.Join(",", cnt);
            if (!d.ContainsKey(key)) {
                d[key] = new List<string>();
            }
            d[key].Add(s);
        }
        return new List<IList<string>>(d.Values);
    }
}

49. Group Anagrams

Description

Solutions

Solution 1: Hash Table

Solution 2: Counting

Comments