Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1233.html

1233. Remove Sub-Folders from the Filesystem

Level

Medium

Description

Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

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^4
  • 2 <= folder[i].length <= 100
  • folder[i] contains only lowercase letters and ‘/’
  • folder[i] always starts with character ‘/’
  • Each folder name is unique.

Solution

Create a class Folder that contains the current folder’s name and a list of its children, which also have type Folder.

Sort the array folder. Use a list to store the root folders that are objects of type Folder. For each folderName in folder, if the list is empty, create a new folder using folderName and add it to the list. Otherwise, loop over existing roots and try to add a subfolder. If a subfolder is added successfully, then it is a subfolder. Otherwise, create a new folder as a root folder and add it to the list.

Finally, loop over the list and add the roots’ names to the result list and return.

  • class Solution {
        public List<String> removeSubfolders(String[] folder) {
            Arrays.sort(folder);
            List<Folder> roots = new ArrayList<Folder>();
            for (String folderName : folder) {
                if (roots.isEmpty()) {
                    Folder newFolder = new Folder(folderName);
                    roots.add(newFolder);
                } else {
                    boolean flag = false;
                    for (Folder root : roots) {
                        boolean addSubfolder = addSubfolder(root, folderName);
                        if (addSubfolder) {
                            flag = true;
                            break;
                        }
                    }
                    if (!flag) {
                        Folder newFolder = new Folder(folderName);
                        roots.add(newFolder);
                    }
                }
            }
            List<String> remainingFolders = new ArrayList<String>();
            for (Folder root : roots) {
                String rootName = root.folderName;
                remainingFolders.add(rootName);
            }
            return remainingFolders;
        }
    
        public boolean addSubfolder(Folder root, String folderName) {
            String rootName = root.folderName;
            if (!folderName.contains(rootName))
                return false;
            String[] rootNameArray = rootName.split("/");
            String[] folderNameArray = folderName.split("/");
            if (rootNameArray.length == folderNameArray.length)
                return false;
            else {
                root.addSubfolder(folderName);
                return true;
            }
        }
    }
    
    class Folder {
        String folderName;
        List<Folder> children;
    
        public Folder() {
            
        }
    
        public Folder(String folderName) {
            this.folderName = folderName;
            children = new ArrayList<Folder>();
        }
    
        public void addSubfolder(String subFolderName) {
            Folder subFolder = new Folder(subFolderName);
            children.add(subFolder);
        }
    }
    
  • // OJ: https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/
    // Time: O(NlogN * W)
    // Space: O(NW)
    struct Node {
        unordered_map<string, Node*> m;
        bool end = false;
    };
    class Solution {
    public:
        vector<string> removeSubfolders(vector<string>& A) {
            Node root;
            sort(begin(A), end(A));
            vector<string> ans;
            for (auto &s : A) {
                string word;
                istringstream ss(s);
                auto node = &root;
                bool skip = false;
                while (getline(ss, word, '/') && !skip) {
                    if (word.empty()) continue;
                    if (node->m.count(word) && node->m[word]->end) skip = true;
                    if (!node->m[word]) node->m[word] = new Node();
                    node = node->m[word];
                }
                if (skip) continue;
                node->end = true;
                ans.push_back(s);
            }
            return ans;
        }
    };
    
  • 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
    
    ############
    
    # 1233. Remove Sub-Folders from the Filesystem
    # https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/
    
    class Solution:
        def removeSubfolders(self, folder: List[str]) -> List[str]:
            folder.sort(key = len)
            s = set()
            res = []
            
            for f in folder:
                path = f.split("/")[1:]
                full = ""
                for p in path:
                    full += p
                    if full in s: break
                else:
                    s.add(full)
                    res.append(f)
        
                    
            
            return res
    
  • 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
    }
    

All Problems

All Solutions