1233. Remove Sub-Folders from the Filesystem

Given a list of folders folder, return  the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

  • For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

  • 1 <= folder.length <= 4 * 104
  • 2 <= folder[i].length <= 100
  • folder[i] contains only lowercase letters and '/'.
  • folder[i] always starts with the character '/'.
  • Each folder name is unique.

这道题给了一堆文件目录的地址,让去除其中所有的子目录,所谓的子目录,就是在父文件夹下的文件,比如 /home/user 这个文件夹下有个叫 grandyang 的文件夹,则 /home/user/grandyang 就是其的一个子目录。既然是子目录,那么路径中肯定有一部分是和父目录相同的,所以可以把所有的父目录都放到一个 HashSet 中,然后遍历某个要检验的路径的所有前缀,若其在 HashSet 中存在,说明当前是个子目录。由于路径越长,其是子目录的可能性就越大,所以可以按照长度先来排个序,先处理那些长度短的路径,同时排序也保证了父目录一定比其子目录先处理。可以从第三个字符开始遍历,因为限定了路径长度至少为2,若遍历到的字符是 ‘/‘,说明前面的部分已经是一个合法的路径,而且可能已经存在了,需要到 HashSet 中检测一下,若存在,后面的部分就不用检测了,直接 break 掉循环。若所有字符成功遍历完,说明当前路径没有父目录,可以加到 HashSet 中。最后循环结束后,把 HashSet 中所有的内容放到数组中返回即可,参见代码如下:

解法一:

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end(), [](string& a, string& b) {return a.size() < b.size();});
        unordered_set<string> seen;
        for (string name : folder) {
            int i = 2, n = name.size();
            for (; i < n; ++i) {
                if (name[i] == '/' && seen.count(name.substr(0, i))) {
                    break;
                }
            }
            if (i == n) seen.insert(name);
        }
        return vector<string>(seen.begin(), seen.end());
    }
};

再来看一种解法,这里不是按路径长度排序,而是按照字母顺序排序,这样相同的父路径的目录就会被放到一起,而且长度短的在前面。此时遍历所有目录,若结果 res 为空,则可以将当前目录加入结果中,因为按照排序后的顺序,肯定不存在当前目录的父目录。若 res 不为空,则将其最后一个目录取出来,并且加上 ‘/‘,看是否是当前路径的前缀,若不是的话就可以将当前路径加入结果 res。想一下为何要在后面加上 ‘/‘ 呢,因为只有加上了才能保证是父目录,比如结果 res 的最后一项为 /a,而当前的路径为 /ab,不加 ‘/‘ 的话,则 /a 也是前缀,就出错了,参见代码如下:

解法二:

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        vector<string> res;
        sort(folder.begin(), folder.end());
        for (string name : folder) {
            if (res.empty() || name.rfind(res.back() + "/", 0) != 0) {
                res.push_back(name);
            }
        }
        return res;
    }
};

这道题的标签中还有前缀树 Trie,表示还可以用这种方法来做。当然首先是要定义前缀树的结构体,这里由于还存在 ‘/‘ 字符,所以很明显 26 个字符是不够用的,则 child 数组可以定义为 27 个,将最后一个位置留给 ‘/‘ 字符,同时这里还需要一个变量 index,表示当前路径在给定路径中的位置,不存在的用 -1 表示,这里相当于一般的前缀树的中的 isWord 标识。接下来先构建前缀树,遍历所有的路径,并且遍历路径上的每一个字符,若是 ‘/‘ 字符,则 idx 为 26,否则是其跟小写字母a之间的距离。若 idx 位置为空,则在该位置上新建 Trie,接下来将指针移动 child[idx] 结点上继续建树。当树建好了之后,就可以开始查找所有的父目录了。这里用 BFS 来遍历,将根结点 root 放到 queue 中,然后开始遍历,取出队首元素,查看若其 index 大于等于0,则将其加入结果 res 中,由于是 BFS 的顺序,则第一个遇到的目录肯定是父目录,然后遍历其 child 结点,若子结点存在,且不是遇到了 ‘/‘ 字符或者 index 小于0,则将当前结点放入 queue 继续遍历,因为遇到 ‘/‘ 字符且 index 大于等于0时,表示是子目录,这种情况应该跳过,参见代码如下:

解法三:

class Solution {
public:
    struct Trie {
        Trie *child[27];
        int index = -1;
    };
    
    vector<string> removeSubfolders(vector<string>& folder) {
        Trie* root = new Trie();
        for (int i = 0; i < folder.size(); ++i) {
            Trie *t = root;
            for (char c : folder[i]) {
                int idx = (c == '/') ? 26 : c - 'a';
                if (!t->child[idx]) t->child[idx] = new Trie();
                t = t->child[idx];
            }
            t->index = i;
        }
        return bfs(folder, root);
    }
    
    vector<string> bfs(vector<string>& folder, Trie* root) {
        vector<string> res;
        queue<Trie*> q{{root}};
        while (!q.empty()) {
            Trie *t = q.front(); q.pop();
            if (t->index >= 0) res.push_back(folder[t->index]);
            for (int i = 0; i < 27; ++i) {
                if (t->child[i] && !(i == 26 && t->index >= 0)) {
                    q.push(t->child[i]);
                }
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1233

参考资料:

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/discuss/409028/JavaPython-3-3-methods-from-O(n-*-(logn-%2B-m-2))-to-O(n-*-m)-w-brief-explanation-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

喜欢请点赞,疼爱请打赏❤️.

微信打赏

|

Venmo 打赏


—|—


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation