从文件系统中删除子文件夹

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中文网其他相关文章！