Постановка задачи :
Вам дан отсортированный (в лексическом порядке) словарь чужого языка. Напишите функцию, которая находит порядок символов в инопланетном языке. Этот словарь будет предоставлен вам в виде массива строк под названием «словарь» размера «N».
Дано
3 a aa aaa
Вывод:
True
Объяснение данных тестовых случаев:
For the test case, the words are 'a', 'aa', and 'aaa'. Since the only unique character here is 'a', so the array to be returned will just be ['a']. The 'true' that is being printed just signifies that the output returned by the function is valid.Подход :
Топологическая сортировка
Здесь, если мы рассмотрим ["wrt", "wrf", ....] первые два слова из словаря инопланетян, то, взглянув на первое несоответствие в символах, мы получим важную информацию о порядке их появления!
Это означает, что из двух приведенных выше слов мы можем сказать, что «t» предшествует «f»! Мы можем обозначить это отношение как «t» → «f».
Мы можем представить это отношение с помощью ориентированного графа!
Следовательно,
- Переберите все слова и постройте график, представляющий указанное выше отношение. Все отдельные символы будут вершинами графа, тогда как отношение, отображающее, какой символ предшествует другому символу, будет направленным ребром.
- Выполните топологическую сортировку над построенным графом и верните один из возможных порядков для него.
Временная сложность: O(N+K)
Пространственная сложность: O(K)
Код :
Спасибо за чтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
