class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
}
};
1233. 删除子文件夹
你是一位系统管理员，手里有一份文件夹列表 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 * 1042 <= folder[i].length <= 100folder[i] 只包含小写字母和 '/'folder[i] 总是以字符 '/' 起始原站题解
java 解法, 执行用时: 60 ms, 内存消耗: 60.1 MB, 提交时间: 2023-02-08 09:58:04
class Trie {
private Map<String, Trie> children = new HashMap<>();
private int fid = -1;
public void insert(int fid, String f) {
Trie node = this;
String[] ps = f.split("/");
for (int i = 1; i < ps.length; ++i) {
String p = ps[i];
if (!node.children.containsKey(p)) {
node.children.put(p, new Trie());
}
node = node.children.get(p);
}
node.fid = fid;
}
public List<Integer> search() {
List<Integer> ans = new ArrayList<>();
dfs(this, ans);
return ans;
}
private void dfs(Trie root, List<Integer> ans) {
if (root.fid != -1) {
ans.add(root.fid);
return;
}
for (var child : root.children.values()) {
dfs(child, ans);
}
}
}
class Solution {
public List<String> removeSubfolders(String[] folder) {
Trie trie = new Trie();
for (int i = 0; i < folder.length; ++i) {
trie.insert(i, folder[i]);
}
List<String> ans = new ArrayList<>();
for (int i : trie.search()) {
ans.add(folder[i]);
}
return ans;
}
}
golang 解法, 执行用时: 148 ms, 内存消耗: 10.3 MB, 提交时间: 2023-02-08 09:57:44
type Trie struct {
children map[string]*Trie
isEnd bool
}
func newTrie() *Trie {
m := map[string]*Trie{}
return &Trie{children: m}
}
func (this *Trie) insert(w string) {
node := this
for _, p := range strings.Split(w, "/")[1:] {
if _, ok := node.children[p]; !ok {
node.children[p] = newTrie()
}
node, _ = node.children[p]
}
node.isEnd = true
}
func (this *Trie) search(w string) bool {
node := this
for _, p := range strings.Split(w, "/")[1:] {
if _, ok := node.children[p]; !ok {
return false
}
node, _ = node.children[p]
if node.isEnd {
return true
}
}
return false
}
func removeSubfolders(folder []string) []string {
sort.Slice(folder, func(i, j int) bool {
return len(strings.Split(folder[i], "/")) < len(strings.Split(folder[j], "/"))
})
trie := newTrie()
var ans []string
for _, v := range folder {
if !trie.search(v) {
trie.insert(v)
ans = append(ans, v)
}
}
return ans
}
javascript 解法, 执行用时: 268 ms, 内存消耗: 71.1 MB, 提交时间: 2023-02-08 09:56:50
/**
* @param {string[]} folder
* @return {string[]}
*/
var removeSubfolders = function(folder) {
const root = new Trie();
for (let i = 0; i < folder.length; ++i) {
const path = split(folder[i]);
let cur = root;
for (const name of path) {
if (!cur.children.has(name)) {
cur.children.set(name, new Trie());
}
cur = cur.children.get(name);
}
cur.ref = i;
}
const ans = [];
const dfs = (folder, ans, cur) => {
if (cur.ref !== -1) {
ans.push(folder[cur.ref]);
return;
}
for (const child of cur.children.values()) {
dfs(folder, ans, child);
}
}
dfs(folder, ans, root);
return ans;
}
const split = (s) => {
const ret = [];
let cur = '';
for (let i = 0; i < s.length; ++i) {
const ch = s[i];
if (ch === '/') {
ret.push(cur);
cur = ''
} else {
cur += ch;
}
}
ret.push(cur);
return ret;
}
class Trie {
constructor() {
this.ref = -1;
this.children = new Map();
}
}
python3 解法, 执行用时: 276 ms, 内存消耗: 44.1 MB, 提交时间: 2023-02-08 09:56:26
# 字典树
class Trie:
def __init__(self):
self.children = dict()
self.ref = -1
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
root = Trie()
for i, path in enumerate(folder):
path = path.split("/")
cur = root
for name in path:
if name not in cur.children:
cur.children[name] = Trie()
cur = cur.children[name]
cur.ref = i
ans = list()
def dfs(cur: Trie):
if cur.ref != -1:
ans.append(folder[cur.ref])
return
for child in cur.children.values():
dfs(child)
dfs(root)
return ans
golang 解法, 执行用时: 56 ms, 内存消耗: 10.1 MB, 提交时间: 2023-02-08 09:54:26
func removeSubfolders(folder []string) []string {
sort.Strings(folder)
ans := []string{folder[0]}
for _, f := range folder[1:] {
m, n := len(ans[len(ans)-1]), len(f)
if m >= n || !(ans[len(ans)-1] == f[:m] && f[m] == '/') {
ans = append(ans, f)
}
}
return ans
}
cpp 解法, 执行用时: 168 ms, 内存消耗: 40 MB, 提交时间: 2023-02-08 09:54:11
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> ans = {folder[0]};
for (int i = 1; i < folder.size(); ++i) {
int m = ans.back().size();
int n = folder[i].size();
if (m >= n || !(ans.back() == folder[i].substr(0, m) && folder[i][m] == '/')) {
ans.emplace_back(folder[i]);
}
}
return ans;
}
};
java 解法, 执行用时: 56 ms, 内存消耗: 50.2 MB, 提交时间: 2023-02-08 09:53:57
class Solution {
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder);
List<String> ans = new ArrayList<>();
ans.add(folder[0]);
for (int i = 1; i < folder.length; ++i) {
int m = ans.get(ans.size() - 1).length();
int n = folder[i].length();
if (m >= n || !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m)) && folder[i].charAt(m) == '/')) {
ans.add(folder[i]);
}
}
return ans;
}
}
python3 解法, 执行用时: 84 ms, 内存消耗: 25.5 MB, 提交时间: 2023-02-08 09:53:44
# 排序遍历
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
folder.sort()
ans = [folder[0]]
for f in folder[1:]:
m, n = len(ans[-1]), len(f)
if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):
ans.append(f)
return ans