妙哉妙哉"/>
LeetCode题目笔记——1233. 删除子文件夹,写法妙哉妙哉
文章目录
- 题目描述
- 题目难度——中等
- 方法一:排序
- 代码/C++
- 代码/Python
- 方法二:字典树
- 总结
题目描述
你是一位系统管理员,手里有一份文件夹列表 folder,你的任务是要删除该列表中的所有 子文件夹,并以 任意顺序 返回剩下的文件夹。
如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下,那么 folder[i] 就是 folder[j] 的 子文件夹 。
文件夹的「路径」是由一个或多个按以下格式串联形成的字符串:‘/’ 后跟一个或者多个小写英文字母。
- 例如,"/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 * 104
- 2 <= folder[i].length <= 100
- folder[i] 只包含小写字母和 ‘/’
- folder[i] 总是以字符 ‘/’ 起始
- 每个文件夹名都是 唯一 的
题目链接
题目难度——中等
方法一:排序
需要判断子文件夹,而父文件夹的字符串一定是子文件夹的前缀,换句话说,子文件夹的长度更长,因此我们可以直接按字典序排序,则可能存在父子关系文件夹的就排在一起了,我们再遍历,进行判断就行了。这里C++代码借鉴了官方题解,因为对vector还不太熟,所以觉得这个写法太妙了。
代码/C++
class Solution {
public:vector<string> removeSubfolders(vector<string>& folder) {sort(folder.begin(), folder.end());vector<string> res = {folder[0]};int i, len = folder.size(), pre;for(i = 1; i < len; i++){if(pre = res.end()[-1].size(); !(pre < folder[i].size() && res.end()[-1] == folder[i].substr(0, pre) && folder[i][pre] == '/')){res.push_back(folder[i]);}}return res;}
};
这里记录一下上面的vector.end()[-1]用法,end方法返回的是一个迭代器,且指向的是vector中最后一个元素的下一个位置,因此如果要获得最后一个元素的话,就要往前走一个位置,上面if里的pre也可以这样写:
pre = (*(res.end() - 1)).size()
代码/Python
class Solution:def removeSubfolders(self, folder: List[str]) -> List[str]:folder.sort()res = [folder[0]]for i in range(1, len(folder)):if not((pre := len(res[-1])) < len(folder[i]) and res[-1] == folder[i][:pre] and folder[i][pre] == '/'):res.append(folder[i])return res
方法二:字典树
还有一种字典树的方法,其实也想到了字典树,但对其还不熟,所以这里也是学习一下官方的方法。
class Trie:def __init__(self):self.children = dict()self.ref = -1class Solution:def removeSubfolders(self, folder: List[str]) -> List[str]:root = Trie()for i, path in enumerate(folder):path = path.split("/")cur = rootfor name in path:if name not in cur.children:cur.children[name] = Trie()cur = cur.children[name]cur.ref = ians = list()def dfs(cur: Trie):if cur.ref != -1:ans.append(folder[cur.ref])returnfor child in cur.children.values():dfs(child)dfs(root)return ans作者:力扣官方题解
链接:/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
总结
排序方法下,排序操作占大头,所以时间复杂度应该是O(logN),空间上面用到了vector,所以是O(N)。
更多推荐
LeetCode题目笔记——1233. 删除子文件夹,写法妙哉妙哉
发布评论