1233。從文件系統(tǒng)中刪除子文件夾

難度：中等

主題：數(shù)組、字符串、深度優(yōu)先搜索、Trie

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

如果文件夾[i]位于另一個文件夾[j]內，則稱為它的子文件夾。 folder[j] 的子文件夾必須以folder[j] 開頭，后跟“/”。例如，“/a/b”是“/a”的子文件夾，但“/b”不是“/a/b/c”的子文件夾。

路徑的格式是一個或多個以下形式的串聯(lián)字符串：“/”后跟一個或多個小寫英文字母。

• 例如，“/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”位于我們文件系統(tǒng)中的文件夾“/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. 將當前元素插入數(shù)組中，然后循環(huán)，直到我們刪除所有子文件夾，重復此操作，直到沒有元素留下。

解決方案：

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

1. 按字典順序對文件夾進行排序：按字典順序對文件夾路徑進行排序可確保任何子文件夾都會立即跟隨其父文件夾。例如，在排序列表中，“/a”后面會跟著“/a/b”，這樣我們就可以輕松檢查子文件夾關系。

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

3. 在 PHP 中實現(xiàn)解決方案：我們跟蹤添加到結果列表中的最后一個文件夾路徑。如果當前文件夾以最后一個文件夾開頭并緊跟一個 /，則它是一個子文件夾，應被忽略。

讓我們用 PHP 實現(xiàn)這個解決方案：1233。從文件系統(tǒng)中刪除子文件夾

<?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() 函數(shù)按字典順序排列文件夾。這樣可以更輕松地查找子文件夾關系，因為子文件夾將直接跟隨其父文件夾。

2. 循環(huán)遍歷每個文件夾:

   • 如果結果為空（第一次迭代）或者當前文件夾路徑不是以最后添加的文件夾后跟 / 開頭，則它不是子文件夾，并且會添加到結果數(shù)組中。
   • 如果它確實以最后一個文件夾路徑開頭并且緊隨其后有一個 /，則它是一個子文件夾，我們會跳過將其添加到結果中。

3. 結果：函數(shù)返回結果，僅包含根文件夾，不包括任何子文件夾。

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

聯(lián)系鏈接

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

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

• 領英
• GitHub

以上是從文件系統(tǒng)中刪除子文件夾的詳細內容。更多信息請關注PHP中文網其他相關文章！