MediumStrings

Group Anagrams

stringhash-mapsorting

Problem

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

Examples

Example 1

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

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

Constraints

•1 <= strs.length <= 10^4
•0 <= strs[i].length <= 100

Hints

Hint 1

Sort each string — anagrams produce the same sorted key. Use a HashMap<String, List<String>>.

Solutions

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);              // anagrams share the same sorted key
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

Java

Time: O(n * k log k) where k = max string length · Space: O(n*k)