Артём слышал, что список фамилий в публикациях сортируют в лексикографическом порядке. Артём очень тщеславен, и пытается придумать, в каком порядке должны идти буквы в алфавите, чтобы его фамилия в публикации стояла первой. Помогите Артёму написать программу которая бы вычисляла такой алфавит, в котором заданный список фамилий был бы лексикографически отсортированным или определяла, что это невозможно.
Программы принимаются на языках Java, Kotlin. В качестве ответа пожалуйста пришлите ссылку на Github с решением.
Вход:
Подается в стандартный ввод. В первой строке записано целое число n (1 ≤ n ≤ 100), количество имен.
В каждой из следующих n строк записано по одному слову name%i , обозначающему i-е имя. Каждое имя содержит только строчные буквы латинского алфавита, не более 100 символов. Все имена различны.
Выход:
Подается в стандартный вывод. Если существует такой порядок букв, при котором имена в данном списке следуют в лексикографическом порядке, выведите любой такой порядок в виде перестановки символов ' a'–'z' (иными словами, выведите сначала первую букву модифицированного алфавита, затем вторую, и так далее).
В противном случае выведите единственное слово «Impossible» (без кавычек).
- Рассмотрим лексикографический порядок как частичный порядок на буквах.
- Построим граф для этого порядка, где вершины — буквы, а ребро — отношение 'меньше', заданное входными данными.
- Свойства частичного порядка — рефлексивность, антисимметричность и транзитивность.
- Петли(рефлексивность) рассматривать не будем для удобства написания кода.
- Из свойств следует, что частичному порядку соответствует ацикличный граф
- Тогда построим граф, найдем топологическую сортировку, попутно проверяя ацикличность
- Найденная топологическая сортировка - алфавит, который удовлетворяет исходному порядку, следовательно является нашим ответом
Мы рассматриваем порядок только на буквах, но у лексикографического порядка есть особенность, что при равенстве букв сравниваются длины строк, поэтому перед построением графа проверим, что строки, одна из которых является префиксом другой, стоят в порядке не убывания длины
Код документирован JavaDoc и комментирован
Считаем строки и проверим, что 'одинаковые' строки стоят в правильном порядке по длине
Будем попарно рассматривать строки и идти до первого несовпадающего символа.
Проведем ребро от буквы меньшей строки к букве из большей, в понимании расположения во входном
файле.\
Для топсорта используем алгоритм с поиском в глубину(dfs
)
Ацикличность проверяется покраской вершин в 3 цвета: нерассмотренные, открытые, закрытые.
Значение dfs - есть ли в поддереве вершина, находящаяся в цикле.
Проверка на корректные длины строк-префиксов - O(n^2)
Топсорт = dfs
— O(|V|+|E|)
. Так как одна строка даёт не больше одного ребра, то |E| = O(|V|)
.
Следовательно, O(|V|)
Итоговая асимптотика - O(n^2)
.
Генерируется случайная перестановка алфавита, генерируются случайные строки из алфавита
Строки сортируются относительно сгенерированного алфавита
Если нужен тест на некорректность, последняя и первая строки меняются местами. Неидеальная реализация, для проверки в рамках этого задания этого достаточно.