Учитывая массив строк, вернуть все группы строк, которые являются анаграммы

Question

Учитывая массив строк, вернуть все группы строк, которые являются анаграммами.

Мои решения:

Для каждого строкового слова в массиве сортируйте его O (m lg m), m - средняя длина слова.

Создание хеш-таблицы <строка, список>.

Поместите отсортированное слово в хеш-таблицу в качестве ключа, а также сгенерируйте все перестановки (O (m!)) Слова, ищите каждую перестановку в словаре (карта дерева префиксов) с O (m), если в словаре поместите (O (1)) в хеш-таблицу, чтобы все переставленные слова были помещены в список с одинаковым ключом.

Всего O (n * m * lg m * m!) Времени и O (n * m!) Пространства, n - размер заданного массива.

Если m очень большое, это не эффективно, m! ,

Есть ли лучшие решения?

спасибо

Answer 1

Мы определяем алфавит, который содержит каждую букву в нашем списке слов.Далее нам нужно различное простое число для каждой буквы в алфавите, я рекомендую использовать наименьшее, которое вы можете найти.

Это даст нам следующее отображение: {a => 2, b => 3,c => 5, d => 7 и т. д.}

Теперь посчитайте буквы в слове, которое вы хотите представить как целое число, и построите свое целое число результата следующим образом:

Псевдокод:

result = 1
for each letter:
....result *= power(prime[letter], count(letter,word)

некоторые примеры:

aaaa => 2 ^ 4

aabb => 2 ^ 2 * 3 ^ 2 = bbaa = baba = ...

и т. Д.

Таким образом, у вас будет целое число, представляющее каждое слово в вашем словаре, и слово, которое вы хотите проверить, сможет быть преобразовано в целое число.Поэтому, если n - это размер вашего словаря, а k - это самое длинное слово, потребуется O (nk), чтобы построить новый словарь, и O (k), чтобы проверить новое слово.

Hackthissite.comесть проблема программирования, которая заключается в следующем: учитывая зашифрованное слово, найдите его в словаре, чтобы увидеть, есть ли какие-либо анаграммы этого слова в словаре.Есть хорошая статья об эффективном решении проблемы, из которой я позаимствовал ответ, также подробно рассматриваются дальнейшие оптимизации.

Answer 2

используйте сортировку подсчета для сортировки слова, чтобы можно было выполнить сортировку в O (m). после сортировки сгенерируйте ключ из слова и вставьте узел (ключ, значение) в хеш-таблицу. Генерация ключа может быть достигнута в O (м).

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

Итак, общая сложность времени O (mn), где n - общее количество слов (размер ввода).

Также по этой ссылке есть решение похожих проблем-> http://yourbitsandbytes.com/viewtopic.php?f=10&t=42

Answer 3

превратить словарь в отображение отсортированных символов слова, сопоставленного каждому слову этих символов, и сохранить его. Для каждого слова, которое вам дано, отсортируйте его и добавьте в список вывод анаграмм из сопоставления.

Answer 4

#include <map>
#include <iostream>
#include <set>
#include <algorithm>

int main () {
  std::string word;
  std::map<std::string, std::set<std::string>> anagrams;
  while(std::cin >> word) {
    std::string sortedWord(word);
    std::sort(sortedWord.begin(), sortedWord.end());
    anagrams[sortedWord].insert(word);
  }
  for(auto& pair : anagrams) {
    for(auto& word : pair.second) {
      std::cout << word << " ";
    }
    std::cout << "\n";
  }
}

Я позволю тому, кто лучше разбирается в биг-о, чем я, выяснить сложности.

Answer 5

Я не верю, что вы можете добиться большего успеха в терминах O, чем

• сортировка букв каждого слова
• сортировка списка отсортированных слов
• каждый набор анаграмм теперь будет сгруппирован последовательно.