LeetCode题目笔记——1233. 删除子文件夹，写法妙哉妙哉

妙哉妙哉"/>

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)。