Description#
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.
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 * 1042 <= folder[i].length <= 100folder[i] contains only lowercase letters and '/'.folder[i] always starts with the character '/'.- Each folder name is unique.
Solutions#
Solution 1: Sorting#
First, we sort the array folder in lexicographical order, then traverse the array. For the current folder $f$ we are traversing, if its length is greater than or equal to the length of the last folder in the answer array, and its prefix includes the last folder in the answer array plus a /, then $f$ is a subfolder of the last folder in the answer array, and we don’t need to add it to the answer array. Otherwise, we add $f$ to the answer array.
After the traversal ends, the folders in the answer array are the answer required by the problem.
The time complexity is $O(n \times \log n \times m)$, and the space complexity is $O(m)$. Where $n$ and $m$ are the length of the array folder and the maximum length of the strings in the array folder, respectively.
1
2
3
4
5
6
7
8
9
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder);
List<String> ans = new ArrayList<>();
ans.add(folder[0]);
for (int i = 1; i < folder.length; ++i) {
int m = ans.get(ans.size() - 1).length();
int n = folder[i].length();
if (m >= n
|| !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m))
&& folder[i].charAt(m) == '/')) {
ans.add(folder[i]);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> ans = {folder[0]};
for (int i = 1; i < folder.size(); ++i) {
int m = ans.back().size();
int n = folder[i].size();
if (m >= n || !(ans.back() == folder[i].substr(0, m) && folder[i][m] == '/')) {
ans.emplace_back(folder[i]);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
| 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
}
|
Solution 2: Trie#
We can use a trie to store all the folders in the array folder. Each node of the trie contains a children field, used to store the child nodes of the current node, and a fid field, used to store the index of the folder corresponding to the current node in the array folder.
For each folder $f$ in the array folder, we first split $f$ into several substrings according to /, then start from the root node and add the substrings to the trie in turn. Next, we start from the root node to search the trie. If the fid field of the current node is not -1, it means that the folder corresponding to the current node is a folder in the answer array. We add it to the answer array and return. Otherwise, we recursively search all child nodes of the current node and finally return the answer array.
The time complexity is $O(n \times m)$, and the space complexity is $O(n \times m)$. Where $n$ and $m$ are the length of the array folder and the maximum length of the strings in the array folder, respectively.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Trie:
def __init__(self):
self.children = {}
self.fid = -1
def insert(self, i, f):
node = self
ps = f.split('/')
for p in ps[1:]:
if p not in node.children:
node.children[p] = Trie()
node = node.children[p]
node.fid = i
def search(self):
def dfs(root):
if root.fid != -1:
ans.append(root.fid)
return
for child in root.children.values():
dfs(child)
ans = []
dfs(self)
return ans
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
trie = Trie()
for i, f in enumerate(folder):
trie.insert(i, f)
return [folder[i] for i in trie.search()]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Trie {
private Map<String, Trie> children = new HashMap<>();
private int fid = -1;
public void insert(int fid, String f) {
Trie node = this;
String[] ps = f.split("/");
for (int i = 1; i < ps.length; ++i) {
String p = ps[i];
if (!node.children.containsKey(p)) {
node.children.put(p, new Trie());
}
node = node.children.get(p);
}
node.fid = fid;
}
public List<Integer> search() {
List<Integer> ans = new ArrayList<>();
dfs(this, ans);
return ans;
}
private void dfs(Trie root, List<Integer> ans) {
if (root.fid != -1) {
ans.add(root.fid);
return;
}
for (var child : root.children.values()) {
dfs(child, ans);
}
}
}
class Solution {
public List<String> removeSubfolders(String[] folder) {
Trie trie = new Trie();
for (int i = 0; i < folder.length; ++i) {
trie.insert(i, folder[i]);
}
List<String> ans = new ArrayList<>();
for (int i : trie.search()) {
ans.add(folder[i]);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class Trie {
public:
void insert(int fid, string& f) {
Trie* node = this;
vector<string> ps = split(f, '/');
for (int i = 1; i < ps.size(); ++i) {
auto& p = ps[i];
if (!node->children.count(p)) {
node->children[p] = new Trie();
}
node = node->children[p];
}
node->fid = fid;
}
vector<int> search() {
vector<int> ans;
function<void(Trie*)> dfs = [&](Trie* root) {
if (root->fid != -1) {
ans.push_back(root->fid);
return;
}
for (auto& [_, child] : root->children) {
dfs(child);
}
};
dfs(this);
return ans;
}
vector<string> split(string& s, char delim) {
stringstream ss(s);
string item;
vector<string> res;
while (getline(ss, item, delim)) {
res.emplace_back(item);
}
return res;
}
private:
unordered_map<string, Trie*> children;
int fid = -1;
};
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
Trie* trie = new Trie();
for (int i = 0; i < folder.size(); ++i) {
trie->insert(i, folder[i]);
}
vector<string> ans;
for (int i : trie->search()) {
ans.emplace_back(folder[i]);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| type Trie struct {
children map[string]*Trie
isEnd bool
}
func newTrie() *Trie {
m := map[string]*Trie{}
return &Trie{children: m}
}
func (this *Trie) insert(w string) {
node := this
for _, p := range strings.Split(w, "/")[1:] {
if _, ok := node.children[p]; !ok {
node.children[p] = newTrie()
}
node, _ = node.children[p]
}
node.isEnd = true
}
func (this *Trie) search(w string) bool {
node := this
for _, p := range strings.Split(w, "/")[1:] {
if _, ok := node.children[p]; !ok {
return false
}
node, _ = node.children[p]
if node.isEnd {
return true
}
}
return false
}
func removeSubfolders(folder []string) []string {
sort.Slice(folder, func(i, j int) bool {
return len(strings.Split(folder[i], "/")) < len(strings.Split(folder[j], "/"))
})
trie := newTrie()
var ans []string
for _, v := range folder {
if !trie.search(v) {
trie.insert(v)
ans = append(ans, v)
}
}
return ans
}
|
Solution 3#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| type Trie struct {
children map[string]*Trie
fid int
}
func newTrie() *Trie {
return &Trie{map[string]*Trie{}, -1}
}
func (this *Trie) insert(fid int, f string) {
node := this
ps := strings.Split(f, "/")
for _, p := range ps[1:] {
if _, ok := node.children[p]; !ok {
node.children[p] = newTrie()
}
node = node.children[p]
}
node.fid = fid
}
func (this *Trie) search() (ans []int) {
var dfs func(*Trie)
dfs = func(root *Trie) {
if root.fid != -1 {
ans = append(ans, root.fid)
return
}
for _, child := range root.children {
dfs(child)
}
}
dfs(this)
return
}
func removeSubfolders(folder []string) (ans []string) {
trie := newTrie()
for i, f := range folder {
trie.insert(i, f)
}
for _, i := range trie.search() {
ans = append(ans, folder[i])
}
return
}
|
