Строковые анаграммы в бегущем потоке

-1

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

Например:

Input: { 'действие', 'кошка', собака ' 'ТАС', 'ABC', 'бог', 'БАК'}

Выход: {' акт ',' cat ',' tac ', dog', 'god', 'abc', 'bac'}

Дополнительные слова могут быть добавлены.

Какой алгоритм или структура данных можно использовать?

источник

2016-02-23 geeky

Для меня совершенно непонятно, когда должна выводиться конкретная строка. –

мы должны разделить заданные строки на группы в основном: например, cat, act и tac будут в одной группе, потому что все эти три строки являются перестановкой друг друга. Аналогично, собака и бог являются анаграммами, поэтому они будут в другой группе. – geeky

Намного понятнее. Также может быть, например, «собака» и «бог» появляются в начале? В конце? В обратном порядке? Пожалуйста, обновите свой вопрос с ответами на все эти вопросы. –

Если вы любите C++, а затем просто хранить их, как это:

unordered_map<string, vector<string> > anagrams; 
void insert(const string& str) { 
    string copy = str; 
    sort(str.begin(), str.end()); 
    anagrams[str].push_back(copy); 
}

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

Я предполагаю, что печать должна быть очевидной.

источник

2016-02-23 06:05:00 iggy

: Не могли бы вы привести небольшой пример – geeky

пример чего? – iggy

Строковые анаграммы в бегущем потоке

ответ

Смежные вопросы