⚡Flashcard Drill➔
NeetCode #479LC-1233MediumTries
← Back to All Problems

#479 · #1233 · Remove Sub-Folders from the Filesystem(删除子文件夹)

📌 Problem Statement & Constraints

Given a list of absolute folder paths folder, remove all sub-folders and return the remaining paths in any order. Constraints: 1 <= folder.length <= 4 * 10^4, 2 <= folder[i].length <= 100.

💡 Core Algorithmic Approaches

  1. Sort the paths lexicographically. Then any sub-folder of a kept folder appears immediately after it (possibly after other sub-folders).
  2. So a single pass suffices: keep a path only if it is not prefixed by the last kept path plus /.
  3. Appending the / is crucial -- without it, /a/bc would be wrongly considered inside /a/b.
  4. Sorting makes this O(n log n) and avoids any trie construction.

💻 Benchmark Python3 Implementation

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()                      # parents come before their children
        res = []
        for f in folder:
            # keep only if not inside the last kept folder
            if not res or not f.startswith(res[-1] + "/"):
                res.append(f)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n * L): the sort dominates.
💾 Space Complexity
O(n) for the result.

⚠️ Interview Pitfalls & Follow-ups

  • Using startswith(res[-1]) without the trailing slash: /a/bc would be treated as inside /a/b.
  • Not sorting: parents and children would not be adjacent, so the single-pass check fails.
  • Building a trie: workable, but sorting is far simpler and equally efficient here.
  • Assuming no duplicates: the input may contain them, and the prefix test handles it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Tries Problems