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

難度：中等

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

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

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

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

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

示例1：

• 輸入：文件夾 = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
• 輸出： ["/a","/c/d","/c/f"]
• 說(shuō)明： 文件夾“/a/b”是“/a”的子文件夾，“/c/d/e”位于我們文件系統(tǒng)中的文件夾“/c/d”內(nèi)。

示例2：

• 輸入：文件夾 = ["/a","/a/b/c","/a/b/d"]
• 輸出： ["/a"]
• 說(shuō)明：文件夾“/a/b/c”和“/a/b/d”將被刪除，因?yàn)樗鼈兪恰?a”的子文件夾。

示例 3：

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

約束：

• 1 4
• 2
• 文件夾[i]僅包含小寫(xiě)字母和“/”。
• 文件夾[i]始終以字符“/”開(kāi)頭。
• 每個(gè)文件夾名稱(chēng)都是唯一。

提示：

1. 按字典順序?qū)ξ募A進(jìn)行排序。
2. 將當(dāng)前元素插入數(shù)組中，然后循環(huán)，直到我們刪除所有子文件夾，重復(fù)此操作，直到?jīng)]有元素留下。

解決方案：

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

1. 按字典順序?qū)ξ募A進(jìn)行排序：按字典順序?qū)ξ募A路徑進(jìn)行排序可確保任何子文件夾都會(huì)立即跟隨其父文件夾。例如，在排序列表中，“/a”后面會(huì)跟著“/a/b”，這樣我們就可以輕松檢查子文件夾關(guān)系。

2. 識(shí)別并過(guò)濾掉子文件夾：我們可以迭代排序的列表，檢查當(dāng)前文件夾路徑是否是先前添加的路徑的子文件夾。如果是，我們就跳過(guò)它。如果沒(méi)有，我們會(huì)將其添加到我們的結(jié)果列表中。

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

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：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"]
?>

解釋?zhuān)?

1. 排序：sort() 函數(shù)按字典順序排列文件夾。這樣可以更輕松地查找子文件夾關(guān)系，因?yàn)樽游募A將直接跟隨其父文件夾。

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

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

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

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

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫(kù) 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來(lái)說(shuō)意義重大！

如果您想要更多類(lèi)似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是從文件系統(tǒng)中刪除子文件夾的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！