Как найти список уникальных кратчайших путей в списке путей?

Question

Представьте, что у меня есть древовидный граф, как показано ниже, где у узла может быть несколько дочерних элементов и т. Д. (У узла может быть только 1 родительский элемент). Если у меня есть список путей вдоль этого графика, как я могу найти подмножество этих путей, которые являются уникальными и самыми короткими?

Пример ввода (список путей):

[1, 2, 3]
[1, 2]
[1, 7]
[1, 8, 9, 10]

Ожидаемый результат:

[1, 2]
[1, 7]
[1, 8, 9, 10]

Путь [1, 2, 3] игнорируется, поскольку он длиннее [1, 2], а путь [1, 8, 9, 10] сохраняется, поскольку он уникален.

Answer 1

Попробуйте построить дерево, используя эти пути. Для каждого пути попробуйте пройти от первого узла пути к последнему узлу пути, установив ребро в последовательный узел. Отметьте последний узел пути как конечный узел после прохождения каждого пути. Если вы обнаружите какой-либо узел, помеченный как лист при прохождении пути, вы перестанете проходить. Также удалите дочерний узел узла, который помечен как листовой узел. Каждый путь от корневого узла до конечного узла в конечном дереве будет вашим ответом. Смотрите рисунок ниже для получения дополнительной информации:

Сложность будет суммой длины всего пути.

Answer 2

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

Это O (n log n) по количеству списков и линейное по количеству элементов во всех списках.