已知目录树全文件、目录路径列表，不使用 IO 求空目录

[imn1]

windows 路径
已知整个目录树所有子目录、文件的路径，str 列表
不考虑虚拟路径（软链硬链 mount/lnk 等）

不实际检查文件 IO，就是 is_dir()这些，单纯通过字符串之间关系，求出没有文件的空目录
有没有较快的方案？

[xiaoming1992]

我只能想到笨办法，两层 for 循环，逐个判断是不是空目录。。。

[gstqc]

有序吗？
有序的话直接双指针，慢指针为目录，快指针为文件，判断文件是否 startswith(目录)
时间复杂度 O(n)

[renmu123]

因为目录是树，如果某个节点不是文件且没有子节点，那么应该就能认定其为空目录

[imn1]

@gstqc #2
有序

@renmu123 #3
这个需要 IO，现在假设就是硬盘离线，只有文件列表，无法检测是否存在文件

[SingeeKing]

对时间空间不是特别敏感的话，直接构建一个 trie 树然后输出叶子结点

[xuanbg]

遍历集合生成一个含文件的集合，然后取差集不就好了吗

[shyrock]

@xuanbg #6 我觉得这个是正解。

[no1xsyzy]

因为「有序」，可知上层目录必定出现在下层目录之前
搞个 set，遍历列表，添加自己，删掉上层。
或者也不用搞 set，新建一个 list，反正能删的肯定是最后一个，检测一下最后一个是上层就 pop 掉就成。

[no1xsyzy]

发现其实没理解问题，现明晰一下：

输入样例：
```
1 /abc/empty1
2 /abc/empty1/empty2
3 /abc/empty1/empty2/empty3
4 /abc/file.ext
```
输出样例：
```
5 /abc/empty1
6 /abc/empty1/empty2
7 /abc/empty1/empty2/empty3
```

输入是否是整个层级？还是末端层级？（即，输入是否包含 L1-2 ？）
输出是否要包含子目录？（即，输出是否包含 L6-7 ？）

[Rheinmetal]

如果可以改进流程 学学 everything wiztree

[aijam]

搞个 trie，找出所有子节点

[Vegetable]

寻找所有叶子节点？
去 leetcode 搜了一下，这道题有点像。
https://leetcode-cn.com/problems/remove-sub-folders-from-the-filesystem/

[mingl0280]

……简单粗暴的办法，你自己建个树改下 dirent

[imn1]

@no1xsyzy #9
输入和你一样，输出 7 就可以了，5/6 都有空的子目录，只是我现在只能做到 5/6/7，单独 7 还没想到

主要想尝试优化一下时间，我原来用双循环+collentions.Counter 可以仅输出 7，但比 groupby 用时稍多一点

[no1xsyzy]

你可以
[former
for former, latter in itertools.zip_longest(paths, paths[1:])
if like_dirname(former) and (latter is None or latter.split(os.sep)[0] != former)]

理论上来说，比较相邻两个，如果前一个不是后一个的父级，则包含前一个，再带上最后一个。
再筛选一下名字像是目录名的。
paths 列表比较长的话可能涉及拷贝有效率问题，可以把 paths[1:] 改成 ipaths 并且在前面加上这两行（也就是造两个同一个列表的正好差一位的迭代器）
ipaths = iter(paths)
next(ipaths)
（或者随手写一个 window(iterable, n=2) 的滑动窗口迭代器）

[no1xsyzy]

@no1xsyzy 不好意思 s/latter\.split(os\.sep)/latter.rsplit(os.sep,1)/

[no1xsyzy]

想到可能有个问题，如果排序是按照字符串而不是目录的话，ASCII 排序有 14 个符号处于 '/' 之前。
/abc/not_empty
/abc/not_empty(but_jump_in)
/abc/not_empty(but_jump_in)/anything
/abc/not_empty/anything
这样的话就会有问题。发现不太确定你的有序是什么意思。
如果是 windows 下，os.sep=='\\' 排序就更混乱了，它在大小写之间……

[liprais]

把你的路径做成接邻表，没有子节点然后是目录的就是你要的

[gstqc]

还是上个样例数据吧
假如

/dir1/
/dir1/file1
/dir1/file2
/dir1/dir2/
/dir1/dir3/
/dir1/dir3/file3
/dir1/dir4/

输出结果是 /dir1/dir2/, /dir1/dir4/？

如果是有序并且这个顺序是 目录->目录文件->子目录->子目录文件 这种
简单的滑动比较就可以了

无序可以考虑构建个多叉树，全部填充完再遍历

[imn1]

@gstqc #19
Y
排序是字符串排序，windows 路径符是\，所以有#17 所说的问题，前面的例子只是偷懒写成 unix 路径 /

补充一个：
输入
/dir1/dir5
/dir1/dir5/dir6
期望只输出
/dir1/dir5/dir6

目前做到是两个都输出了