Вы когда-нибудь слышали о словаре пришельцев?

Что ж, если вы этого не сделали, вы упускаете очень важную проблему кодирования!

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

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

Если вы не знаете, в чем проблема, мы вам поможем. Прочитайте все, что вам нужно знать о проблеме здесь.

Постановка проблемы

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

Здесь вам необходимо найти порядок, в котором будут появляться символы словаря пришельцев.

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

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

Чтобы лучше понять проблему, рассмотрим следующий пример:

Вам дан следующий порядок словаря = {"baa", "abcd". «Abca», «cab», «cad»}

Здесь вывод будет BDAC

Пояснение:

Для начала вам нужно будет сравнить исходные две строки. Первые буквы этих строк отличаются друг от друга. Следовательно, мы пришли к выводу, что A является преемником B в словаре пришельцев.

Кроме этого, мы не будем использовать никакие другие буквы из этих строк. Теперь мы сравним следующие две строки, и вы увидите, что abc присутствует в обеих из них. Здесь, в этих строках, d и варьируются, и поэтому мы пришли к выводу, что A является преемником D. Точно так же мы сделали другие предположения, например, A присутствует до C, а D является преемником B.

Вот почему мы пришли к выводу, что порядок символов в инопланетном словаре будет B D A C

Оптимальное решение проблемы со словарем пришельцев

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

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

Для этого нам необходимо выполнить следующие операции:

  • Для начала выполните итерацию предоставленного вектора строк, а затем сравните последовательные строки буква за буквой. Когда в строках наблюдается несоответствие, вам нужно будет добавить к вашему графику ребро, направленное от буквы, присутствующей в строке U, к букве, присутствующей в строке V.
  • Теперь, когда ваш ациклический граф готов, вам нужно будет выполнить для него топологическую сортировку и определить порядок символов.

Если вы не знаете, как выполнять топологическую сортировку, давайте разберемся, что это такое и как это работает!

Понимание топологической сортировки

Топологическая сортировка определяется как вертикальное упорядочение вершин ориентированного ациклического графа таким образом, что для каждого ребра, направленного из u в v, вершина u будет стоять перед v в порядке.

Здесь вам нужно знать одну вещь: вы не можете выполнять топологическую сортировку, если не используете граф DAG.

Алгоритм топологической сортировки

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

Следующие шаги выполняются в топологическом порядке:

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

Подход к топологической сортировке

  • Начните с создания стека для хранения всех узлов.
  • Объявите массив размером N для хранения узлов, которые вы уже посетили.
  • Теперь вам нужно запустить цикл в пределах от 0 до N
  • В случае, если узел не посещен и помечен как True, необходимо вызвать рекурсивную функцию и выполнить следующие шаги:
  • Вам нужно пометить текущий узел как True в массиве, содержащем посещенные узлы.
  • Затем запустите цикл для всех узлов, содержащих направленное ребро текущего узла.
  • В случае, если узел не отмечен, вам необходимо вызвать функцию топологической сортировки на узле
  • Добавьте текущий узел в свой стек.
  • В конце вам нужно будет распечатать элементы, присутствующие в вашем стеке.

Анализ сложности

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

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

  • Временная сложность: временная сложность этого метода рассчитывается как O(m*n) + O(d+n)= O(m*n). Здесь n — количество строк, а m — количество символов, присутствующих в каждой строке.
  • Пространственная сложность: космическая сложность этого метода рассчитывается как O(d+n) + O(d)= O(d+n).

Заключение

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

Однако, если вы хотите улучшить свои знания в области кодирования и укрепить свои основы, присоединиться к обучению ниндзя — лучший вариант для вас.