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

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

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

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

Псевдокод:

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

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

аааа => 2^4

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

и так далее.

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

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

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

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

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

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

#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";
  }
}

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

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

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

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