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 }