1233.删除子文件夹

链接：1233.删除子文件夹
难度：Medium
标签：深度优先搜索、字典树、数组、字符串
简介：你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

题解 1 - cpp

• 编辑时间：2023-02-08
• 执行用时：208ms
• 内存消耗：51.4MB
• 编程语言：cpp
• 解法介绍：trie。

struct Node {
    bool end;
    unordered_map<string, Node*> children;
    Node(): end(false) {}
};
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        Node *root = new Node();
        vector<string> ans;
        for (auto &path : folder) {
            Node *next = root;
            istringstream iss(path);
            string tmp;
            getline(iss, tmp, '/');
            while (getline(iss, tmp, '/')) {
                if (!next->children.count(tmp)) next = next->children[tmp] = new Node();
                else next = next->children[tmp];
                if (next->end) break;
            }
            if (!next->end) ans.push_back(path);
            next->end = true;
        }
        return ans;
    }
};

题解 2 - python

• 编辑时间：2023-02-08
• 执行用时：140ms
• 内存消耗：25.4MB
• 编程语言：python
• 解法介绍：同上。

class Node:
    def __init__(self) -> None:
        self.end = False
        self.children = defaultdict(Node)
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        root = Node()
        ans = []
        for path in folder:
            nextNode = root
            l = path.split('/')
            for i in range(1, len(l)):
                nextNode = nextNode.children[l[i]]
                if nextNode.end:
                    break
            if not nextNode.end:
                ans.append(path)
            nextNode.end = True
        return ans

题解 3 - rust

• 编辑时间：2023-02-08
• 执行用时：56ms
• 内存消耗：6.8MB
• 编程语言：rust
• 解法介绍：同上。

use std::collections::HashMap;
#[derive(Clone)]
struct Node {
    end: bool,
    children: HashMap<String, Node>,
}
impl Node {
    fn new() -> Self {
        Self {
            end: false,
            children: HashMap::new(),
        }
    }
}
impl Solution {
    pub fn remove_subfolders(folder: Vec<String>) -> Vec<String> {
        let mut folder = folder;
        folder.sort();
        let mut root = Node::new();
        let mut ans = vec![];
        for path in folder {
            let mut next = &mut root;
            let l: Vec<&str> = path.split("/").collect();
            for i in 1..l.len() {
                if !next.children.contains_key(l[i]) {
                    next.children.insert(l[i].to_string(), Node::new());
                }
                next = next.children.get_mut(l[i]).unwrap();
                if next.end {
                    break;
                }
            }
            if !next.end {
                ans.push(path);
            }
            next.end = true;
        }
        ans
    }
}