Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Group anagrams challenge

Sharing is caring!

Problem statement
An anagram is a word that can be written as a permutation of the characters of another word, like “dirty room” and “dormitory” (ignore spaces). However, “the” and “thee” are not anagrams, since “the” only has a single “e” whereas “thee” has two “e” characters (spaces can occur zero, or multiple times, however.)

Given a list of words as strings, written in lowercase characters a-z, you should return another list of strings, each containing words that are mutual anagrams.

Each string of the output should be a single group of anagarms joined with commas.

Within an output string, the expression should be sorted lexicographically. If a group contains only a single element, output that one-element group as a single string. And the string should be also output in lexicographical order. Given e.g.:

pear
amleth
dormitory
tinsel
dirty room
hamlet
listen
silnet

… the output would be:

amleth, hamlet
dirty room, dormitory
listen, silnet, tinsel
pear

Solution

public class GroupAnagrams {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        Map> map = new HashMap<>();
        while (in.hasNext()) {
            String word = in.nextLine();
            int[] keyArr = new int[26];
            for (char c : word.replaceAll(" ", "").toCharArray()) {
                keyArr[c - 'a'] = keyArr[c - 'a'] + 1;
            }
            String key = Arrays.toString(keyArr);

            if (!map.containsKey(key)) {
                map.put(key, new TreeSet<>());
            }

            map.get(key).add(word);
        }

        for (String key : map.keySet()) {
            String out = map.get(key).toString();
            System.out.println(out.substring(1, out.length() - 1));
        }
    }
}

Above the key is build up as a sequence of the number of appearances of each character in the alphabet. We could also use the characters of the word in sorted order as a key (since anagram words will appear the same when sorted). Although sorting will have a runtime of \mathcal{O}(klogk) with k being the length of the word.

String word = in.nextLine();
char[] keyArr = word.replaceAll(" ", "").toLowerCase().toCharArray();
Arrays.sort(keyArr);
String key = new String(keyArr);
...
map.get(key).add(word);
...