## [f]izzbuzzer

### 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<>());
}

}

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);
...