1233. Remove Sub Folders from the Filesystem

Problem Statement

1233. Remove Sub-Folders from the Filesystem

Medium

Given a list of folders folder, return the folders after removing all sub-folders in those folders. You may return the answer in any order.

If a folder[i] is located within another folder[j], it is called a sub-folder of it. A sub-folder of folder[j] must start with folder[j], followed by a "/". For example, "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c".

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

1 <= folder.length <= 4 * 10⁴
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and '/'.
folder[i] always starts with the character '/'.
Each folder name is unique.

Java — 2pass trie

Source file

class Solution {
    private class TrieNode {
        Map<String, TrieNode> children = new HashMap<>();
        boolean isVisited = false;
    }

    private class Trie {
        TrieNode root;

        Trie() {
            root = new TrieNode();
        }

        void insert(String folder) {
            String[] path = folder.split("/");
            TrieNode curr = root;
            for (String dir : path) {
                curr.children.putIfAbsent(dir, new TrieNode());
                curr = curr.children.get(dir);
                if(curr.isVisited)  // skip traversing a nested path of already seen dir
                    return;
            }
            curr.children.clear();  // clear subfolders encountered previously
            curr.isVisited = true;
        }

        boolean contains(String folder) {
            String[] path = folder.split("/");
            TrieNode curr = root;
            for (String dir : path) {
                if(!curr.children.containsKey(dir))
                    return false;
                curr = curr.children.get(dir);
            }
            return curr.isVisited;
        }
    }

    public List<String> removeSubfolders(String[] folder) {
        Trie trie = new Trie();
        for (String f : folder)
            trie.insert(f);
        List<String> prunedFolderList = new ArrayList<>();
        for(String f: folder)
            if(trie.contains(f))
                prunedFolderList.add(f);
        return prunedFolderList;
    }
}

Java — sort+trie

Source file

class Solution {
    private class TrieNode {
        Map<String, TrieNode> children = new HashMap<>();
        boolean isVisited = false;
    }

    private class Trie {
        TrieNode root;

        Trie() {
            root = new TrieNode();
        }

        boolean insert(String folder) {
            String[] path = folder.split("/");
            TrieNode curr = root;
            for (String dir : path) {
                curr.children.putIfAbsent(dir, new TrieNode());
                curr = curr.children.get(dir);
                if (curr.isVisited)
                    return false;
            }
            return curr.isVisited = true;
        }
    }

    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> prunedFolderList = new ArrayList<>();
        Trie trie = new Trie();
        for (String f : folder)
            if (trie.insert(f))
                prunedFolderList.add(f);
        return prunedFolderList;
    }
}

Java

Source file

class TrieNode {
    Map<String, TrieNode> dir = new HashMap<>();
    boolean vis = false;
    public String toString(){
        return dir.toString() + "\t" + vis;
    }
}
class Trie {
    public TrieNode root;
    Trie(){
        root = new TrieNode();
    }
    public String toString(){
        return root.toString();
    }
}
class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Trie trie = new Trie();
        for(String s: folder){
            String[] subdirs = s.split("/");
            TrieNode tn = trie.root;
            for(String d: subdirs){
                tn.dir.putIfAbsent(d, new TrieNode());
                tn = tn.dir.get(d);
            }
            tn.vis = true;
        }
        List<String> ans = new ArrayList<>();
        // System.out.println(trie);
        for(String s: folder){
            String[] subdirs = s.split("/");
            TrieNode tn = trie.root;
            boolean isSubFolder = false; 
            for(String d: subdirs){
                if(tn.vis){
                    isSubFolder = true;
                    break;
                }
                tn = tn.dir.get(d);
            }
            if(!isSubFolder)
                ans.add(s);
        }
        return ans;
    }
}

Problem Statement