1233。從檔案系統中刪除子資料夾
難度:中
主題:陣列、字串、深度優先搜尋、Trie
給定資料夾列表,返回刪除這些資料夾中的所有子資料夾後的資料夾。您可以按任意順序返回答案。
如果資料夾[i]位於另一個資料夾[j]內,則稱為它的子資料夾。 folder[j] 的子資料夾必須以folder[j] 開頭,後面接著「/」。例如,“/a/b”是“/a”的子資料夾,但“/b”不是“/a/b/c”的子資料夾。
路徑的格式是一個或多個以下形式的串聯字串:「/」後面跟著一個或多個小寫英文字母。
範例1:
範例2:
範例 3:
約束:
提示:
解:
我們可以結合使用排序和字串比較。以下步驟概述了 PHP 中的解決方案:
按字典順序對資料夾進行排序:按字典順序對資料夾路徑進行排序可確保任何子資料夾都會立即跟隨其父資料夾。例如,在排序清單中,“/a”後面會跟著“/a/b”,這樣我們就可以輕鬆檢查子資料夾關係。
識別並過濾掉子資料夾:我們可以迭代排序的列表,檢查當前資料夾路徑是否是先前新增的路徑的子資料夾。如果是,我們就跳過它。如果沒有,我們會將其添加到我們的結果清單中。
在 PHP 中實作解決方案:我們追蹤新增到結果清單中的最後一個資料夾路徑。如果當前資料夾以最後一個資料夾開頭並緊接一個 /,則它是一個子資料夾,應被忽略。
讓我們用 PHP 實作這個解:1233。從檔案系統中刪除子資料夾
<?php /** * @param String[] $folder * @return String[] */ function removeSubfolders($folders) { ... ... ... /** * go to ./solution.php */ } // Test cases $folder1 = ["/a","/a/b","/c/d","/c/d/e","/c/f"]; $folder2 = ["/a","/a/b/c","/a/b/d"]; $folder3 = ["/a/b/c","/a/b/ca","/a/b/d"]; print_r(removeSubfolders($folder1)); // Output: ["/a","/c/d","/c/f"] print_r(removeSubfolders($folder2)); // Output: ["/a"] print_r(removeSubfolders($folder3)); // Output: ["/a/b/c","/a/b/ca","/a/b/d"] ?>
排序:sort() 函數依字典順序排列資料夾。這樣可以更輕鬆地找到子資料夾關係,因為子資料夾將直接跟隨其父資料夾。
循環遍歷每個資料夾:
結果:函數傳回結果,只包含根資料夾,不包含任何子資料夾。
由於排序步驟,此方法的時間複雜度為O(n log n),且線性掃描的時間複雜度為O(n ),使其成為問題約束內較大輸入的良好解決方案。
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
以上是從檔案系統中刪除子資料夾的詳細內容。更多資訊請關注PHP中文網其他相關文章!