題目描述:給定一個資料夾路徑陣列 folder,每條路徑以 / 開頭。若路徑 b 是路徑 a 的子目錄(即 b 以 a + "/" 為前綴),則移除 b。回傳移除所有子目錄後的剩餘路徑。
解題思路(排序 + 線性掃描):
排序後,所有子目錄必定緊跟在其父目錄之後(字典序相鄰)。因此只需一次線性掃描即可判斷每條路徑是否為前一個被保留路徑的子目錄。
步驟:
folder 陣列排序(字典序)。last 為空字串,遍歷每條路徑 f:
f 不以 last + "/" 為前綴,則 f 是頂層路徑,加入結果,並更新 last = f。f 是 last 的子目錄,跳過。為何需要在 last 後加 "/":避免路徑 /a 被誤判為 /ab 的父目錄。前綴必須以 / 結尾才能確保是真正的子目錄關係。
時間複雜度: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,每個節點代表一個路徑段。插入時若某節點已被標記為「終止」(即某路徑在此結束),則後續插入的所有子路徑均被過濾。查詢時 DFS 遍歷 Trie,遇到終止節點即輸出並停止往下搜尋。時間 O(n · L),空間 O(n · L)(所有路徑字元),邏輯清晰但程式碼較長。
將所有路徑存入 unordered_set,對每條路徑逐層去掉最後一個 / 後的段落,檢查是否有祖先路徑存在。若不存在任何祖先則保留。時間最壞 O(n · L²)(路徑深度 × 字串操作),空間 O(n · L),效率不如排序法。
對排序後的陣列,對每條路徑用二分搜尋找是否有前綴路徑存在。與線性掃描等效但多了二分的 log 因子,不如方法一簡潔。