删除子文件夹

记住「排序让父在子前 → 只和上一个保留项比 + 斜杠前缀」。那个斜杠是关键:它把 /a/b(子目录)和 /ab(同级别的另一个目录)区分开。

先看原始输入:[/c/d, /a, /a/b, /c/d/e, /ab],顺序是乱的,/a 和它的子目录 /a/b 没挨着。直接两两比会很费劲。

第一步先按字典序排序。字典序里,前缀更短的字符串排在前,所以每个父目录都会落到它子目录的前面。

按字典序排序,得到 [/a, /a/b, /ab, /c/d, /c/d/e]。注意 /a 排在 /a/b 前、/c/d 排在 /c/d/e 前——父一定在子之前,这正是后面只比「上一个保留项」就够的底气。

结果列表 ans 先清空。接下来从左往右扫每个路径,只和 ans 里最后一个保留项比。

轮到第 0 个 /a(紫)。此刻 ans 还是空的,没有可比的保留项。

先看 ans:还是空的,没有上一个保留项可比,那它直接就该留下。

ans 是空的,/a 当然要保留(标绿),它成为新的「上一个保留项」。

轮到第 1 个 /a/b(紫)。ans 里最后一个保留项是 /a(蓝),拿它来比。

把 /a/b 和「/a/」(上一个保留项 /a 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。

判定:/a/b 以「/a/」开头(连斜杠一起),说明它就在 /a 这个目录里面,是子文件夹,跳过(标灰),不进 ans。

轮到第 2 个 /ab(紫)。ans 里最后一个保留项是 /a(蓝),拿它来比。

把 /ab 和「/a/」(上一个保留项 /a 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。

判定:/ab 虽然也以 /a 这几个字打头,但下一个字符不是斜杠(是「b」),所以它不是 /a 的子目录,而是另一个目录,保留(标绿)。这就是那个斜杠的作用。

轮到第 3 个 /c/d(紫)。ans 里最后一个保留项是 /ab(蓝),拿它来比。

把 /c/d 和「/ab/」(上一个保留项 /ab 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。

判定:/c/d 不以「/ab/」开头,它是个新的目录,保留(标绿),成为新的「上一个保留项」。

轮到第 4 个 /c/d/e(紫)。ans 里最后一个保留项是 /c/d(蓝),拿它来比。

把 /c/d/e 和「/c/d/」(上一个保留项 /c/d 再加个斜杠)逐字符比一比,看它是不是以这个前缀开头。

判定:/c/d/e 以「/c/d/」开头(连斜杠一起),说明它就在 /c/d 这个目录里面,是子文件夹,跳过(标灰),不进 ans。

扫完全程:绿色 [/a, /ab, /c/d] 是保留下来的,灰色 /a/b、/c/d/e 是被删的子文件夹。回头看,排序加一遍扫描就搞定,关键全在「排序让父在子前」和那个分隔斜杠。

再回顾一遍:排序让每个父目录排到子目录前,于是扫描时只需拿当前路径和「上一个保留项 + 斜杠」做一次前缀判断,就能定出它是不是子文件夹,省掉了和所有保留项逐个比较。绿色 [/a, /ab, /c/d] 即答案。

边界:斜杠区分同名前缀、互不包含则全留、深层子目录也只看上一个保留项。

两个高频追问:可用 Trie 免排序;排序让父在子前是因为父是子的前缀。