假设我有一个如下所示的树形图，其中一个节点可以有多个子节点，依此类推..(一个节点只能有 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] 路径被保留，因为它是唯一的。
最佳答案
首先，按长度对输入路径进行排序。维护一组叶节点。这将包含每个有效路径的最后一个节点。添加叶节点后，我们将禁止任何包含该叶节点的路径。添加路径时，请根据叶节点集检查其每个成员。如果获得匹配，则路径无效，否则路径有效，您应该将其最终元素添加到叶节点集中。
列表数量为 O(n log n)，所有列表中的元素数量为线性。
关于algorithm - 如何在路径列表中找到唯一的最短路径列表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53187409/