Alg.14 Group Anagrams

From algoexpert.io

Anagrams are strings made up of exactly the same letters, in this problem, we need to write a function that takes in an array of strings and groups anagrams together. Here is an example:



In the solution, we iterate the original string array, we use Arrays.sort() to sort each string, then store the sorted string and original string into a map. Here is the code implementation:

public static List<List<String>> groupAnagrams(List<String> words) {
    
        Map<String, List<String>> anagrams = new HashMap<>();
        
        for (String word : words) {
            char[] charArray = word.toCharArray();
            Arrays.sort(charArray);
            String sortedWord = new String(charArray);
            
            if (anagrams.containsKey(sortedWord)) anagrams.get(sortedWord).add(word);
            else anagrams.put(sortedWord, new ArrayList<String>(Arrays.asList(word)));
        }
        
        List<List<String>> ans = new ArrayList<>();
        for (List<String> value : anagrams.values()) {
            ans.add(value);
        }
    return ans;
  }

For time complexity: we need to sort each string, wnlogn; Space complexity is pretty straightforward, wn. (w is the number of words, n is the length of the longest string)

Donate