c++ - 按最顶部合并文件夹列表

Question

我正在寻找一种算法，该算法将获取文件夹列表并返回“最少”顶级文件夹的列表。

换句话说，假设我的输入是:

/abc/sub
/abc
/xxx/yyy/zzz
/xxx/yyy/zzz/iii/foobar
/www/zzz
/www/zzz/ppp
/www/xxx

输出应该是

/abc
/xxx/yyy/zzz
/www/zzz
/www/xxx

我可以自由使用 Boost 库，如果有一种简单的方法可以测试某个文件夹是否是层次结构中任意更高层的另一个文件夹的子文件夹，这可能会有所帮助，但我找不到类似的东西。

我在我的实验中不断回过头来的解决方案呈指数级复杂。我想知道我是否遗漏了什么，是否有更好的方法。

谢谢!

Answer 1

你构建了一个 trie ，每个节点都是路径组件。所以当你看到第一条路径时，/abc/sub ，你的 trie 有两个节点:

abc
  - sub

当您看到 /abc ，您检查 trie 并看到它已经作为顶级节点存在，但是您添加一个空引用作为子节点以指示您看到路径名作为输入，后面没有任何内容。然后你得到下一个，/xxx/yyy/zzz ，你的结构变成:

abc
  - <empty>
  - sub
      - <empty>
xxx
  - yyy
      - zzz
          - <empty>

完成后，您的完整 trie 是:

abc
  - empty
  - sub
      - <empty>
xxx
  - yyy
      - zzz
          - <empty>
          - iii
              - foobar
                  - <empty>
www
  - zzz
      - <empty>
      - ppp
  - xxx
      - <empty>

<empty>条目意味着您已经看到在该节点终止的引用。也就是说，您看到了 /xxx/yyy/zzz , 但你从未见过 /xxx/yyy完全靠自己。

现在，您可以遍历 trie 以生成输出，使用您定义的任何规则来表示“最低”顶级。我认为您的意思是您想要不分支的最高级别节点。