##### Welcome to Subscribe On Youtube

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

# 1233. Remove Sub-Folders from the Filesystem

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);
} else {
boolean flag = false;
for (Folder root : roots) {
flag = true;
break;
}
}
if (!flag) {
Folder newFolder = new Folder(folderName);
}
}
}
List<String> remainingFolders = new ArrayList<String>();
for (Folder root : roots) {
String rootName = root.folderName;
}
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 {
return true;
}
}
}

class Folder {
String folderName;
List<Folder> children;

public Folder() {

}

public Folder(String folderName) {
this.folderName = folderName;
children = new ArrayList<Folder>();
}

Folder subFolder = new Folder(subFolderName);
}
}

• // 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:
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
}