Question

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

49	Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:
	[
	  ["ate", "eat","tea"],
	  ["nat","tan"],
	  ["bat"]
	]

Note:
    For the return value, each inner list's elements must follow the lexicographic order.
    All inputs will be in lower-case.

@tag-hashtable

Algorithm

With sort

How to judge whether the two are misplaced words? It can be found that if the character order of the misplaced words is rearranged, the same result will be obtained. Therefore, reordering is a way to judge whether the two are misplaced words.

Use the same string as the key, save all misplaced words in the string array, and establish a mapping between the key and the number of different sets of misplaced words. The reason why there is no dislocation between the key and its membership is established here The mapping between word sets uses a small trick to avoid copying the set in the HashMap to the result res at the end.

When it is detected that the current word is not in the HashMap, it is known that the word will belong to a new set of misplaced words, so it is mapped to the number of the current set of misplaced words, and then an empty set is added to res, so that You can directly find the position of the new misplaced word set through its mapping value, so as to 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

Java

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

}

All Problems

All Solutions