跳转至

1233. 删除子文件夹

题目描述

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。folder[j] 的子文件夹必须以 folder[j] 开头，后跟一个 "/"。例如，"/a/b" 是 "/a" 的一个子文件夹，但 "/b" 不是 "/a/b/c" 的一个子文件夹。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

  • 例如，"/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] 总是以字符 '/' 起始
  • folder 每个元素都是 唯一 的

解法

方法一：排序

我们先将数组 folder 按照字典序排序，然后遍历数组，对于当前遍历到的文件夹 $f$，如果它的长度大于等于答案数组中最后一个文件夹的长度，并且它的前缀包含答案数组的最后一个文件夹再加上一个 /，则说明 $f$ 是答案数组中最后一个文件夹的子文件夹，我们不需要将其加入答案数组中。否则，我们将 $f$ 加入答案数组中。

遍历结束后，答案数组中的文件夹即为题目要求的答案。

时间复杂度 $O(n \times \log n \times m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为数组 folder 的长度和数组 folder 中字符串的最大长度。

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
}

1
2
3
4
function removeSubfolders(folder: string[]): string[] {
    let s = folder[1];
    return folder.sort().filter(x => !x.startsWith(s + '/') && (s = x));
}

1
2
3
4
function removeSubfolders(folder) {
    let s = folder[1];
    return folder.sort().filter(x => !x.startsWith(s + '/') && (s = x));
}

方法二：字典树

我们可以使用字典树存储数组 folder 中的所有文件夹。字典树的每个节点包含 children 字段，用于存储当前节点的子节点，以及 fid 字段，用于存储当前节点对应的文件夹在数组 folder 中的下标。

对于数组 folder 中的每个文件夹 $f$，我们先将 $f$ 按照 / 分割成若干个子串，然后从根节点开始，依次将子串加入字典树中。接下来，我们从根节点开始搜索字典树，如果当前节点的 fid 字段不为 -1，则说明当前节点对应的文件夹是答案数组中的一个文件夹，我们将其加入答案数组并且返回。否则，我们递归地搜索当前节点的所有子节点，最终返回答案数组。

时间复杂度 $O(n \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 和 $m$ 分别为数组 folder 的长度和数组 folder 中字符串的最大长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Trie:
    def __init__(self):
        self.children = {}
        self.fid = -1

    def insert(self, i, f):
        node = self
        ps = f.split('/')
        for p in ps[1:]:
            if p not in node.children:
                node.children[p] = Trie()
            node = node.children[p]
        node.fid = i

    def search(self):
        def dfs(root):
            if root.fid != -1:
                ans.append(root.fid)
                return
            for child in root.children.values():
                dfs(child)

        ans = []
        dfs(self)
        return ans


class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for i, f in enumerate(folder):
            trie.insert(i, f)
        return [folder[i] for i in trie.search()]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Trie {
public:
    void insert(int fid, string& f) {
        Trie* node = this;
        vector<string> ps = split(f, '/');
        for (int i = 1; i < ps.size(); ++i) {
            auto& p = ps[i];
            if (!node->children.count(p)) {
                node->children[p] = new Trie();
            }
            node = node->children[p];
        }
        node->fid = fid;
    }

    vector<int> search() {
        vector<int> ans;
        function<void(Trie*)> dfs = [&](Trie* root) {
            if (root->fid != -1) {
                ans.push_back(root->fid);
                return;
            }
            for (auto& [_, child] : root->children) {
                dfs(child);
            }
        };
        dfs(this);
        return ans;
    }

    vector<string> split(string& s, char delim) {
        stringstream ss(s);
        string item;
        vector<string> res;
        while (getline(ss, item, delim)) {
            res.emplace_back(item);
        }
        return res;
    }

private:
    unordered_map<string, Trie*> children;
    int fid = -1;
};

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        Trie* trie = new Trie();
        for (int i = 0; i < folder.size(); ++i) {
            trie->insert(i, folder[i]);
        }
        vector<string> ans;
        for (int i : trie->search()) {
            ans.emplace_back(folder[i]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function removeSubfolders(folder: string[]): string[] {
    const createTrie = (): T => ({ '#': false, children: {} });
    const trie = createTrie();

    for (const f of folder) {
        const path = f.split('/');
        path.shift();

        let node = trie;
        for (const p of path) {
            if (!node.children[p]) node.children[p] = createTrie();
            node = node.children[p];
        }
        node['#'] = true;
    }

    const ans: string[] = [];
    const dfs = (trie: T, path = '') => {
        if (trie['#']) {
            ans.push(path);
            return;
        }

        for (const key in trie.children) {
            dfs(trie.children[key], path + '/' + key);
        }
    };

    dfs(trie);

    return ans;
}

type T = {
    '#': boolean;
    children: Record<string, T>;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function removeSubfolders(folder) {
    const createTrie = () => ({ '#': false, children: {} });
    const trie = createTrie();

    for (const f of folder) {
        const path = f.split('/');
        path.shift();

        let node = trie;
        for (const p of path) {
            if (!node.children[p]) node.children[p] = createTrie();
            node = node.children[p];
        }
        node['#'] = true;
    }

    const ans = [];
    const dfs = (trie, path = '') => {
        if (trie['#']) {
            ans.push(path);
            return;
        }

        for (const key in trie.children) {
            dfs(trie.children[key], path + '/' + key);
        }
    };

    dfs(trie);

    return ans;
}

方法三

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
type Trie struct {
    children map[string]*Trie
    fid      int
}

func newTrie() *Trie {
    return &Trie{map[string]*Trie{}, -1}
}

func (this *Trie) insert(fid int, f string) {
    node := this
    ps := strings.Split(f, "/")
    for _, p := range ps[1:] {
        if _, ok := node.children[p]; !ok {
            node.children[p] = newTrie()
        }
        node = node.children[p]
    }
    node.fid = fid
}

func (this *Trie) search() (ans []int) {
    var dfs func(*Trie)
    dfs = func(root *Trie) {
        if root.fid != -1 {
            ans = append(ans, root.fid)
            return
        }
        for _, child := range root.children {
            dfs(child)
        }
    }
    dfs(this)
    return
}

func removeSubfolders(folder []string) (ans []string) {
    trie := newTrie()
    for i, f := range folder {
        trie.insert(i, f)
    }
    for _, i := range trie.search() {
        ans = append(ans, folder[i])
    }
    return
}

评论