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

Question

假设我有一个如下所示的 TreeMap ，其中一个节点可以有多个子节点，依此类推。(一个节点只能有一个父节点)。如果我有沿着该图的路径列表，我如何才能找到这些路径的唯一且最短的子集？

示例输入(路径列表):

[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) 和所有列表中元素数量的线性关系。