Show problems as
Classic problem #1233MediumArrayStringDepth-First SearchTrie

Remove Sub-Folders from the Filesystem

Real-world version: Backup Roots Only
Tracked in this browser only
Read Remove Sub-Folders from the Filesystem on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A backup tool is handed a list of directory paths in folder, in no particular order. Each path starts with / and its directory names are separated by /, for example /store/rack/shelf names the directory shelf inside rack inside store.

A path is nested when another path in the list names one of its ancestor directories: /store/rack/shelf is nested when /store or /store/rack is also listed. Matching is by whole directory names, so /store/rackham is not nested inside /store/rack even though the text of one begins with the text of the other.

Backing up a directory covers everything under it, so the tool drops every nested path. Return the paths that survive, sorted in ascending lexicographic order by their characters.

Examples

Example 1

Input
folder = ["/store/rack", "/store/rackham", "/store/rack/shelf", "/store"]
Output
["/store"]

`/store` is listed, so `/store/rack` and `/store/rackham` are both nested inside it, and `/store/rack/shelf` is nested too. Only `/store` survives.

Example 2

Input
folder = ["/a/b", "/a/bc"]
Output
["/a/b", "/a/bc"]

Neither path names an ancestor of the other: `b` and `bc` are different directory names inside `/a`, and `/a` itself is not in the list.

Example 3

Input
folder = ["/p", "/p/q/r"]
Output
["/p"]

`/p` is an ancestor of `/p/q/r`, even though the directory `/p/q` between them is not listed, so the deeper path is dropped.

Constraints

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] consists of lowercase English letters and '/'.
  • folder[i] starts with '/' and does not end with '/'.
  • All paths in folder are distinct.
  • The result is sorted in ascending lexicographic order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_subfolders(folder: list[str]) -> list[str]:
Java
public List<String> removeSubfolders(String[] folder)

More on the same topics