解題說明
Remove Sub-Folders from the Filesystem
題目描述：給定一個資料夾路徑陣列 folder，每條路徑以 / 開頭。若路徑 b 是路徑 a 的子目錄（即 b 以 a + "/" 為前綴），則移除 b。回傳移除所有子目錄後的剩餘路徑。
解題思路（排序 + 線性掃描）：
排序後，所有子目錄必定緊跟在其父目錄之後（字典序相鄰）。因此只需一次線性掃描即可判斷每條路徑是否為前一個被保留路徑的子目錄。
步驟：
- 對
folder陣列排序（字典序）。 - 初始化
last為空字串，遍歷每條路徑f：- 若
f不以last + "/"為前綴，則f是頂層路徑，加入結果，並更新last = f。 - 否則，
f是last的子目錄，跳過。
- 若
- 回傳結果陣列。
為何需要在 last 後加 "/"：避免路徑 /a 被誤判為 /ab 的父目錄。前綴必須以 / 結尾才能確保是真正的子目錄關係。
C++ 解法
複雜度分析
時間複雜度：O(n · L · log n) — 排序需 O(n log n) 次字串比較，每次比較最長路徑長度 O(L)；線性掃描為 O(n · L)，整體由排序主導。
空間複雜度：O(L) — 排序為原地進行，last 儲存一條路徑，額外空間為 O(L)（不計輸出）。
虛擬碼
1. Sort folder array lexicographically.
2. Initialize result = [], last = "".
3. For each path f in folder:
a. If last is empty OR f does NOT start with (last + "/"):
- Append f to result.
- Set last = f.
b. Else: skip f (it is a sub-folder of last).
4. Return result.其他解法
方法二：Trie（字典樹）
將每條路徑按 / 分割後插入 Trie，每個節點代表一個路徑段。插入時若某節點已被標記為「終止」（即某路徑在此結束），則後續插入的所有子路徑均被過濾。查詢時 DFS 遍歷 Trie，遇到終止節點即輸出並停止往下搜尋。時間 O(n · L)，空間 O(n · L)（所有路徑字元），邏輯清晰但程式碼較長。
方法三：Hash Set 查找父路徑
將所有路徑存入 unordered_set，對每條路徑逐層去掉最後一個 / 後的段落，檢查是否有祖先路徑存在。若不存在任何祖先則保留。時間最壞 O(n · L²)（路徑深度 × 字串操作），空間 O(n · L)，效率不如排序法。
方法四：排序 + 二分搜尋
對排序後的陣列，對每條路徑用二分搜尋找是否有前綴路徑存在。與線性掃描等效但多了二分的 log 因子，不如方法一簡潔。
延伸思考
- 若路徑數量 n 達到 10⁶，且路徑平均長度達到 300，排序法與 Trie 法各自的瓶頸在哪裡？如何優化記憶體使用？
- 若問題改為「找出所有深度恰好為 d 的路徑」（根為第 0 層），如何在排序或 Trie 的基礎上快速回答？
- 若路徑中含有符號連結（symlink），子目錄的定義會如何改變，演算法需要做哪些修正？