Medium

题目描述

给你一个文件夹列表 folder，你需要移除其中所有的子文件夹，返回剩余的文件夹。你可以按任意顺序返回答案。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么它就是 folder[j] 的子文件夹。folder[j] 的子文件夹必须以 folder[j] 开头，后跟 "/"。例如，"/a/b" 是 "/a" 的子文件夹，但 "/b" 不是 "/a/b/c" 的子文件夹。

文件夹的格式是一个或多个连接的字符串，格式为：'/' 后跟一个或多个小写英文字母。

例如，"/leetcode" 和 "/leetcode/problems" 都是有效路径，而空字符串和 "/" 不是。

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释：文件夹 "/a/b" 是 "/a" 的子文件夹，"/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都是 "/a" 的子文件夹。

示例 3：

输入：folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出：["/a/b/c","/a/b/ca","/a/b/d"]

提示：

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] 只包含小写字母和 '/'
  • folder[i] 总是以字符 '/' 开头
  • 每个文件夹名都是唯一的

解题思路

这个问题的核心是识别和移除子文件夹。有两种主要的解法思路：

方法一：排序 + 前缀匹配（推荐） 利用字典序排序的特性，如果一个文件夹是另一个文件夹的子文件夹，那么在排序后它一定紧跟在其父文件夹附近。我们可以先对文件夹数组进行排序，然后遍历数组，对于每个文件夹，检查它是否是前一个加入结果的文件夹的子文件夹。

判断子文件夹的条件：

  1. 当前文件夹路径以某个已存在路径开头
  2. 在路径后必须紧跟 ‘/’ 字符

方法二：Trie 树 构建 Trie 树来存储所有路径，每个节点代表路径中的一个目录名。对于每个路径，如果在遍历过程中遇到了标记为结束的节点，说明当前路径是某个已存在路径的子路径。

第一种方法更简单高效，时间复杂度主要是排序的 O(n log n)，空间复杂度 O(1)（不考虑结果数组）。第二种方法虽然概念更清晰，但实现复杂度较高。

代码实现

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        vector<string> result;
        
        for (const string& path : folder) {
            if (result.empty() || !isSubfolder(result.back(), path)) {
                result.push_back(path);
            }
        }
        
        return result;
    }
    
private:
    bool isSubfolder(const string& parent, const string& child) {
        if (child.length() <= parent.length()) {
            return false;
        }
        return child.substr(0, parent.length()) == parent && child[parent.length()] == '/';
    }
};

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        result = []
        
        for path in folder:
            if not result or not self.is_subfolder(result[-1], path):
                result.append(path)
        
        return result
    
    def is_subfolder(self, parent: str, child: str) -> bool:
        if len(child) <= len(parent):
            return False
        return child.startswith(parent) and child[len(parent)] == '/'

public class Solution {
    public IList<string> RemoveSubfolders(string[] folder) {
        Array.Sort(folder);
        var result = new List<string>();
        
        foreach (string path in folder) {
            if (result.Count == 0 || !IsSubfolder(result[result.Count - 1], path)) {
                result.Add(path);
            }
        }
        
        return result;
    }
    
    private bool IsSubfolder(string parent, string child) {
        if (child.Length <= parent.Length) {
            return false;
        }
        return child.StartsWith(parent) && child[parent.Length] == '/';
    }
}

var removeSubfolders = function(folder) {
    folder.sort();
    const result = [];
    
    for (let i = 0; i < folder.length; i++) {
        if (result.length === 0 || !folder[i].startsWith(result[result.length - 1] + '/')) {
            result.push(folder[i]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
排序 + 前缀匹配O(n log n + m)O(1)

其中 n 是文件夹数量，m 是所有文件夹路径的总长度。时间复杂度主要由排序决定，空间复杂度为 O(1)（不计算结果数组的空间）。