Remove Sub-Folders from the Filesystem

摘要

This text analyzes the "Remove Sub-folders from the Filesystem" LeetCode problem and presents two solution approaches. Method 1 uses a Trie (prefix tree) data structure: define trie nodes, insert all files into the tree, then use DFS traversal to collect parent nodes. Method 2 uses sorting: sort files lexicographically, add the first file to results, then traverse remaining elements to check if each is a subfolder of the last added element. For the Trie approach, time complexity is O(nl) and space complexity is O(nl), where n is array length and l is average folder length. For the Sort approach, time complexity is O(nl⋅logn) due to sorting, and space complexity is O(l) for temporary string operations during prefix comparisons.

别着急，坐和放宽

Question

Analysis

Method 1: Trie(Prefix tree)

define trie node structure
insert all file into tree
using DFS traverse to collect parent node

Method 2: Sort

sort by lexicographic order
add the first file into array ans, obviously
traverse remaining elements, determine whether the current element is a sub of the last element of the ans array
yes: ignore; no, add current element into array ans

Timing

NULL

Code

/**
* Trie
*/
public class Solution {

    private TrieNode root;

    public Solution() {
        root = new TrieNode();
    }

    public void insert(String folder, int refValue) {
        TrieNode current = root;
        String[] parts = folder.split("/");
        for (String part : parts) {
            if (!part.isEmpty()) {
                current = current.getChildren().computeIfAbsent(part, k -> new TrieNode());
            }
        }
        current.setRef(refValue); // Store the folder reference
    }

    public boolean search(String folder) {
        return false;
    }

    public List<String> removeSubfolders(String[] folder) {
        for (int i = 0; i < folder.length; i++) {
            insert(folder[i], i);
        }
        List<String> ans = new ArrayList<>();
        dfs(root, ans, folder);
        return ans;
    }

    private void dfs(TrieNode node, List<String> ans, String[] folder) {
        if (node.getRef() != -1) {
            ans.add(folder[node.getRef()]);
            return;
        }
        for (Map.Entry<String, TrieNode> entry : node.getChildren().entrySet()) {
            TrieNode childNode = entry.getValue();
            dfs(childNode, ans, folder);
        }
    }

    class TrieNode {
        private final Map<String, TrieNode> children = new HashMap<>();
        private int ref = -1;

        public Map<String, TrieNode> getChildren() {
            return children;
        }

        public void setRef(int ref) {
            this.ref = ref;
        }

        public int getRef() {
            return ref;
        }
    }
}


/**
* Sort
*/
class Solution {
    public List<String> removeSubfolders(String[] folder) {
        List<String> ans = new ArrayList<>();
        Arrays.sort(folder);
        ans.add(folder[0]);
        for (int i = 1; i < folder.length; i++) {
            String curr = folder[i];
            int currLen = curr.length();
            String prev = ans.get(ans.size() - 1);
            int prevLen = prev.length();
            if (currLen > prevLen && curr.startsWith(prev) && curr.charAt(prevLen) == '/') {
                // current folder is a subfolder of the last added folder
                continue;
            }
            ans.add(curr);
        }
        return ans;
    }
}

Completixy

Trie

Time O(nl), where n and l are the length of the array folder and the average length of a folder, respectively. This is the time required to construct the dictionary tree and the answer.

Space O(nl) is the space required by the dictionary tree.

Sort

Time O(nl⋅logn), where n and l are the length of the array folder and the average length of the folder respectively. O(nl⋅logn) is the time required for sorting, and the time required for constructing the answer is O(nl), which is asymptotically smaller than the former.

Space O(l). When constructing the answer to compare prefixes, we used the string substring operation, so O(l) temporary space is required.