Remove Sub-Folders from the Filesystem

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.