Back to Arrays & Hashing
Medium
Group Anagrams
Given an array of strings `strs`, group the anagrams together. You can return the answer in any order. Anagrams will have the same character counts, so we can use this property to group them.
Examples
Input:strs = ["eat","tea","tan","ate","nat","bat"]
Output:[["bat"],["nat","tan"],["ate","eat","tea"]]
The strings are grouped based on their anagram properties.
Constraints
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i] consists of lowercase English letters.
Approach
Iterate through each string in the array. Sort the characters of the string. Anagrams will become exactly the same string after sorting. Use this sorted string as a key in a hash map, and append the original string to the list of values for that key.
Complexity Analysis
Time Complexity
O(m * n log n)
Space Complexity
O(m * n)
m is the number of strings and n is the maximum length of a string. Sorting each string takes O(n log n).
Solution.java
class Solution { public List<List<String>> groupAnagrams(String[] strs) { if (strs == null || strs.length == 0) return new ArrayList<>(); // Map sorted string to list of anagrams Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { char[] chars = s.toCharArray(); Arrays.sort(chars); String sortedStr = new String(chars); map.putIfAbsent(sortedStr, new ArrayList<>()); map.get(sortedStr).add(s); } return new ArrayList<>(map.values()); }}