Алгоритм поиска анаграмм Java

Question

У меня есть массив Strings в Java. Мне нужно найти анаграммы из массива и распечатать их на экране.

У меня возникли проблемы с частью, где я должен сравнивать элементы массива, чтобы проверить, анаграммы они или нет. Как бы я это сделал? Я должен был бы сделать цикл, чтобы пройти через массив.

Я думаю, что я мог бы отсортировать String с и затем сравнить их (так как если бы они были анаграммами, они будут содержать одинаковые буквы в том же порядке при сортировке), но как мне отменить их, чтобы получить оригинал слово

Answer 1

Если вы алфавитируете буквы, а не хешируете их, они должны быть одинаковыми ...

Map<String, List<String>> words = new HashMap<String, List<String>>();
for(String word : incomingWords) {
   final String key = alphabetize(word);
   if(words.contains(key)){
      words.get(key).add(word);
   } else {
      words.put(key, new ArrayList<String>());
      words.get(key).add(word);
   }
}

Теперь у вас есть Map слов, которые являются анаграммами ... У вас также будет List с в Map, которые имеют только 1 запись, вы можете удалить их с карты, чтобы просто сохранить Map из тех, которые имеют другие анаграммы из вашего словаря ...

Answer 2

Вы можете использовать Map, который отображает упорядоченный String в Collection индексов массива, которые являются анаграммами упорядоченного String.