algorithm - 如何在路径列表中找到唯一最短路径列表？

Question

想象一下，我有一个如下所示的树形图，其中一个节点可以有多个子节点，依此类推......（一个节点只能有一个父节点）。如果我有一个沿该图的路径列表，我如何找到这些路径中唯一且最短的子集？

示例输入（路径列表）：

[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

首先，按长度对输入路径进行排序。维护一组叶节点。这将包含每个有效路径的最后一个节点。添加叶节点后，我们将禁止任何包含该叶节点的路径。添加路径时，请根据叶节点集检查其每个成员。如果您得到匹配，则路径无效，否则它是有效的，您应该将它的最终元素添加到叶节点集。

这是列表数量的 O(n log n) 和所有列表中元素数量的线性关系。

Answer 2

尝试使用这些路径构建一棵树。对于每条路径，通过设置edge为连续节点，尝试从路径的第一个节点遍历到路径的最后一个节点。遍历完每条路径后，将路径的最后一个节点标记为叶子节点。如果在遍历路径时发现任何标记为叶子的节点，您将停止遍历。同时删除标记为叶节点的节点的子节点。最终树中从根节点到叶节点的每条路径都是您的答案。更多说明请参见下图：

复杂度将是所有路径长度的总和。