You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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".
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;
}
};
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 anotherfolder[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."/leetcode"
and"/leetcode/problems"
are valid paths while an empty string and"/"
are not.Example 1:
Example 2:
Example 3:
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'/'
.这道题给了一堆文件目录的地址,让去除其中所有的子目录,所谓的子目录,就是在父文件夹下的文件,比如
/home/user
这个文件夹下有个叫 grandyang 的文件夹,则/home/user/grandyang
就是其的一个子目录。既然是子目录,那么路径中肯定有一部分是和父目录相同的,所以可以把所有的父目录都放到一个 HashSet 中,然后遍历某个要检验的路径的所有前缀,若其在 HashSet 中存在,说明当前是个子目录。由于路径越长,其是子目录的可能性就越大,所以可以按照长度先来排个序,先处理那些长度短的路径,同时排序也保证了父目录一定比其子目录先处理。可以从第三个字符开始遍历,因为限定了路径长度至少为2,若遍历到的字符是 '/',说明前面的部分已经是一个合法的路径,而且可能已经存在了,需要到 HashSet 中检测一下,若存在,后面的部分就不用检测了,直接 break 掉循环。若所有字符成功遍历完,说明当前路径没有父目录,可以加到 HashSet 中。最后循环结束后,把 HashSet 中所有的内容放到数组中返回即可,参见代码如下:解法一:
再来看一种解法,这里不是按路径长度排序,而是按照字母顺序排序,这样相同的父路径的目录就会被放到一起,而且长度短的在前面。此时遍历所有目录,若结果 res 为空,则可以将当前目录加入结果中,因为按照排序后的顺序,肯定不存在当前目录的父目录。若 res 不为空,则将其最后一个目录取出来,并且加上 '/',看是否是当前路径的前缀,若不是的话就可以将当前路径加入结果 res。想一下为何要在后面加上 '/' 呢,因为只有加上了才能保证是父目录,比如结果 res 的最后一项为
/a
,而当前的路径为/ab
,不加 '/' 的话,则/a
也是前缀,就出错了,参见代码如下:解法二:
这道题的标签中还有前缀树 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时,表示是子目录,这种情况应该跳过,参见代码如下:
解法三:
Github 同步地址:
#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 打赏
---|---
The text was updated successfully, but these errors were encountered: