從檔案系統中刪除子資料夾

1233。從檔案系統中刪除子資料夾

難度：中

主題：陣列、字串、深度優先搜尋、Trie

給定資料夾列表，返回刪除這些資料夾中的所有子資料夾後的資料夾。您可以按任意順序返回答案。

如果資料夾[i]位於另一個資料夾[j]內，則稱為它的子資料夾。 folder[j] 的子資料夾必須以folder[j] 開頭，後面接著「/」。例如，“/a/b”是“/a”的子資料夾，但“/b”不是“/a/b/c”的子資料夾。

路徑的格式是一個或多個以下形式的串聯字串：「/」後面跟著一個或多個小寫英文字母。

• 例如，「/leetcode」和「/leetcode/problems」是有效路徑，而空字串和「/」則不是。

範例1：

• 輸入：資料夾 = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
• 輸出： ["/a","/c/d","/c/f"]
• 說明： 資料夾「/a/b」是「/a」的子資料夾，「/c/d/e」位於我們檔案系統中的資料夾「/c/d」內。

範例2：

• 輸入：資料夾 = ["/a","/a/b/c","/a/b/d"]
• 輸出： ["/a"]
• 說明：資料夾「/a/b/c」和「/a/b/d」將被刪除，因為它們是「/a」的子資料夾。

範例 3：

• 輸入：資料夾 = ["/a/b/c","/a/b/ca","/a/b/d"]
• 輸出： ["/a/b/c","/a/b/ca","/a/b/d"]

約束：

• 1 4
• 2
• 資料夾[i]僅包含小寫字母和“/”。
• 資料夾[i]始終以字元“/”開頭。
• 每個資料夾名稱都是唯一。

提示：

1. 依字典順序對資料夾進行排序。
2. 將目前元素插入陣列中，然後循環，直到我們刪除所有子資料夾，重複此操作，直到沒有元素留下。

解：

我們可以結合使用排序和字串比較。以下步驟概述了 PHP 中的解決方案：

1. 按字典順序對資料夾進行排序：按字典順序對資料夾路徑進行排序可確保任何子資料夾都會立即跟隨其父資料夾。例如，在排序清單中，“/a”後面會跟著“/a/b”，這樣我們就可以輕鬆檢查子資料夾關係。

2. 識別並過濾掉子資料夾：我們可以迭代排序的列表，檢查當前資料夾路徑是否是先前新增的路徑的子資料夾。如果是，我們就跳過它。如果沒有，我們會將其添加到我們的結果清單中。

3. 在 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"]
?>

解釋：

1. 排序：sort() 函數依字典順序排列資料夾。這樣可以更輕鬆地找到子資料夾關係，因為子資料夾將直接跟隨其父資料夾。

2. 循環遍歷每個資料夾:

   • 如果結果為空（第一次迭代）或目前資料夾路徑不是以最後新增的資料夾後跟 / 開頭，則它不是子資料夾，並且會新增到結果陣列中。
   • 如果它確實以最後一個資料夾路徑開頭並且緊接著有一個 /，則它是一個子資料夾，我們會跳過將其添加到結果中。

3. 結果：函數傳回結果，只包含根資料夾，不包含任何子資料夾。

由於排序步驟，此方法的時間複雜度為O(n log n)，且線性掃描的時間複雜度為O(n )，使其成為問題約束內較大輸入的良好解決方案。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是從檔案系統中刪除子資料夾的詳細內容。更多資訊請關注PHP中文網其他相關文章！