Question

Formatted question description: https://leetcode.ca/all/49.html

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⁴
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Algorithm

With sort

To determine whether two words are misplaced, we can check if rearranging the characters of one word produces the other. Therefore, we can use reordering as a method to identify misplaced words.

To implement this, we can use the same string as a key and store all misplaced words in a string array. We can then establish a mapping between the key and the number of different sets of misplaced words. To avoid copying the set in the HashMap to the result res at the end, we establish a mapping between word sets and their membership using a small trick.

If we detect that the current word is not in the HashMap, we know that the word belongs to a new set of misplaced words. We can then map the word to the number of the current set of misplaced words and add an empty set to res. This allows us to directly find the position of the new misplaced word set through its mapping value and store the new word in the result.

No sort

Use an int array with a size of 26 to count the number of occurrences of characters in each word, and then convert the int array into a unique string, and map it with the string array, so that there is no need to sort the strings.

Code

public class Group_Anagrams {

    public static void main(String[] args) {
        Group_Anagrams out = new Group_Anagrams();

        System.out.println(out.groupAnagrams(new String[]{"", ""}));

        System.out.println(out.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));

        char[] a = new char[]{'c','b','a'};
        Arrays.sort(a);
        System.out.println(a);
    }

    // eg: abbccc will be #1#2#3#0#0#0...#0
    //
    // Time Complexity: O(NK)
    // Space Complexity: O(NK)
    class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {

            if (strs.length == 0) {
                return new ArrayList<>();
            }

            Map<String, List<String>> hm = new HashMap<>();
            for (String each: strs) {
                String key = getKey(each);

                if (!hm.containsKey(key)) {
                    hm.put(key, new ArrayList<>());
                }

                hm.get(key).add(each);
            }

            return new ArrayList<>(hm.values());
        }

        // abbccc will be #1#2#3#0#0#0...#0
        //             or 123000...000       <= better key
        private String getKey(String s) {

            int[] count = new int[26];
            for (char each: s.toCharArray()) {
                count[each - 'a']++;
            }

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < count.length; i++) {
                sb.append(count[i]);
            }

            return sb.toString();
        }
    }

    // Time Complexity: O(NKlogK)
    // Space Complexity: O(NK)
    public List<List<String>> groupAnagrams(String[] array) {
        List<List<String>> list = new ArrayList<List<String>>();

        if (array == null) {
            return list;
        }

        HashMap<String, List<String>> hm = new HashMap<>();
        for (String each: array) {		// M * (NlogN + N) => M * NlogN
            // sort-2
            char[] charArray = each.toCharArray();
            Arrays.sort(charArray);
            // String sorted = charArray.toString(); // @note: return: getClass().getName() + '@' + Integer.toHexString(hashCode())

            // String sorted = new String(charArray); // @note: correct way to convert char[] to string
            // String sorted = String.valueOf(charArray); // @note: correct way to convert char[] to string
            String sorted = String.copyValueOf(charArray); // @note: correct way to convert char[] to string



            if (hm.containsKey(sorted)) {
                hm.get(sorted).add(each);
            } else {
                ArrayList<String> al = new ArrayList<String>();

                al.add(each);
                hm.put(sorted, al);
            }
        }

        list.addAll(hm.values());

        return list;
    }

}

############

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

// OJ: https://leetcode.com/problems/group-anagrams/
// Time: O(NWlogW)
// Space: O(NW)
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& A) {
        unordered_map<string, vector<string>> m;
        for (auto &s : A) {
            auto key = s;
            sort(begin(key), end(key));
            m[key].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto &[key, strs] : m) ans.push_back(strs);
        return ans;
    }
};

'''
>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> d["a"]=1
>>> d["b"]=2
>>> d
defaultdict(<class 'list'>, {'a': 1, 'b': 2})
>>> d.values()
dict_values([1, 2])
>>> list(d.values())
[1, 2]

### sorted(str) will return a list of chars
>>> a = "sdfddxyz"
>>> sorted(a)
['d', 'd', 'd', 'f', 's', 'x', 'y', 'z']
>>> "".join(sorted(a))
'dddfsxyz'
'''

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(object):
  def groupAnagrams(self, strs):
    """
    :type strs: List[str]
    :rtype: List[List[str]]
    """

    def hash(count):
      p1, p2 = 2903, 29947
      ret = 0
      for c in count:
        ret = ret * p1 + c
        p1 *= p2
      return ret

    d = {}

    for str in strs:
      count = [0] * 26
      for c in str:
        count[ord(c) - ord('a')] += 1
      key = hash(count)
      if key not in d:
        d[key] = [str]
      else:
        d[key].append(str)
    return [d[k] for k in d]

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[][] {
    let map = new Map();
    for (let str of strs) {
        let arr = str.split('');
        arr.sort();
        let key = arr.join('');
        let value = map.get(key) ? map.get(key) : [];
        value.push(str);
        map.set(key, value);
    }
    return Array.from(map.values());
}

using System.Collections.Generic;

public class Comparer : IEqualityComparer<string>
{
    public bool Equals(string left, string right)
    {
        if (left.Length != right.Length) return false;

        var leftCount = new int[26];
        foreach (var ch in left)
        {
            ++leftCount[ch - 'a'];
        }

        var rightCount = new int[26];
        foreach (var ch in right)
        {
            var index = ch - 'a';
            if (++rightCount[index] > leftCount[index]) return false;
        }

        return true;
    }

    public int GetHashCode(string obj)
    {
        var hashCode = 0;
        for (int i = 0; i < obj.Length; ++i)
        {
            hashCode ^= 1 << (obj[i] - 'a');
        }
        return hashCode;
    }
}

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        var dict = new Dictionary<string, List<string>>(new Comparer());
        foreach (var str in strs)
        {
            List<string> list;
            if (!dict.TryGetValue(str, out list))
            {
                list = new List<string>();
                dict.Add(str, list);
            }
            list.Add(str);
        }
        foreach (var list in dict.Values)
        {
            list.Sort();
        }
        return new List<IList<string>>(dict.Values);
    }
}

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut map = HashMap::new();
        for s in strs {
            let key = {
                let mut arr = s.chars().collect::<Vec<char>>();
                arr.sort();
                arr.iter().collect::<String>()
            };
            let val = map.entry(key).or_insert(vec![]);
            val.push(s);
        }
        map.into_iter().map(|(_, v)| v).collect()
    }
}

49 - Group Anagrams

Question

Algorithm

With sort

No sort

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

With sort

No sort

Code

All Problems

All Solutions