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
- Sort the paths lexicographically. Then any sub-folder of a kept folder appears immediately after it (possibly after other sub-folders).
- So a single pass suffices: keep a path only if it is not prefixed by the last kept path plus
/. - Appending the
/is crucial -- without it,/a/bcwould be wrongly considered inside/a/b. - 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/bcwould 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.