Print Anagrams Together

JavaView on GFG

Problem Overview

Group strings that are anagrams of each other.

Intuition

Group strings that are anagrams of each other. Use sorted string as key.

Algorithm

1For each string: sort its characters to get key.
2Group by key using a map. Return groups.

Common Pitfalls

• Maintain insertion order for group stability. Sort each string O(L*logL) where L is max length.

Print Anagrams Together.java

Java

// Approach: Sort each word's characters to get a key. Group words by their sorted key using a HashMap.
// Time: O(n * k log k) Space: O(n * k)
class Solution {
    public ArrayList<ArrayList<String>> anagrams(String[] arr) {
        ArrayList<ArrayList<String>> res = new ArrayList<>();
        HashMap<String, Integer> mp = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            String s = arr[i];
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            s = new String(chars);
            if (!mp.containsKey(s)) {
                mp.put(s, res.size());
                res.add(new ArrayList<>());
            }
            res.get(mp.get(s)).add(arr[i]);
        }
        return res;
    }
}

Was this solution helpful?