My no-brainer solution is by sorting the input list by its length since subfolder will always be longer than its root. Then add to a hashset if not exists for each of its subfolders. def removeSubfolders(self, folder: List[str]) -> List[str]: roots = set() folder.sort(key=len) for i in folder: temp = i[1:].split("/") string = "" found = False for temp_str in temp: string += "/" + temp_str if string in roots: found = True break if found == False: roots.add(string) return list(roots) Adding early stop on the check loop helps the performance a little. On my end, the runtime is 40ms. This is not the optimal solution, but it works.
Instead of sorting by length, we can also do regular list sorting so that the largest folder will be at the end of the list. So, we only need to check if the current folder is a sub folder of the last root folder def is_sub(f1, f2): for i in range(len(f1)): if f1[i] != f2[i]: return False return True folder.sort() ans = ['/'] for f in folder: if not is_sub(ans[-1].split('/'), f.split('/')): ans.append(f) return ans[1:]
another way is to sort the folder and then check while inserting in the trie if the path already exists, it it exists return False else add the path to trie and return True it improves both time and space
Thanks for the great explanation for both approaches! One thing I could suggest for improving the Trie approach is after creating the the full Trie structure, dfs through it with an accumulating path array, and each time a node is found where end_of_folder is true, push the current path (as a string) to a result list, and then backtrack. That way you could potentially cut down on repeated work from that prefix_search method.
Very easy solution 23ms Beats95.00% class Solution: def removeSubfolders(self, folder: List[str]) -> List[str]: # Sort folders lexicographically folder.sort() result = [] for f in folder: # Check if f is a sub-folder of the last added folder if not result or not f.startswith(result[-1] + '/'): result.append(f) return result
Simple Hashmap solution : var removeSubfolders = function (folder) { let output = [] let map = {} for (let i = 0; i < folder.length; i++) { map[folder[i]] = true } for (let i = 0; i < folder.length; i++) { let eachFolder = folder[i].split("/").slice(1) let subFolder = "" let count = 0 for (let k = 0; k < eachFolder.length; k++) { subFolder += '/' + eachFolder[k] if (map[subFolder]) { count++ } } if (count == 1) { output.push(folder[i]) } } return output };
Tomorrow: Split a String Into the Max Number of Unique Substrings 10/26: The Knight’s Tour 10/27: Minimum Number of Removals to Make Mountain Array 10/28: Count Square Submatrices with All Ones 10/29: Height of Binary Tree After Subtree Removal Queries
r u dropping hints, will that dismantle the botnet finally? i've been overindulging obliviousness bc my vagus nerve is 1 mm from rupturing, 22 yr old me would've boiled my laptop in risen and other chemicals needed to boil laptops. also cool algorithm video or whatever, very smart. - 4 year old desperately in need of being spoken to like a 4 year old
My no-brainer solution is by sorting the input list by its length since subfolder will always be longer than its root. Then add to a hashset if not exists for each of its subfolders.
def removeSubfolders(self, folder: List[str]) -> List[str]:
roots = set()
folder.sort(key=len)
for i in folder:
temp = i[1:].split("/")
string = ""
found = False
for temp_str in temp:
string += "/" + temp_str
if string in roots:
found = True
break
if found == False:
roots.add(string)
return list(roots)
Adding early stop on the check loop helps the performance a little. On my end, the runtime is 40ms. This is not the optimal solution, but it works.
Instead of sorting by length, we can also do regular list sorting so that the largest folder will be at the end of the list. So, we only need to check if the current folder is a sub folder of the last root folder
def is_sub(f1, f2):
for i in range(len(f1)):
if f1[i] != f2[i]:
return False
return True
folder.sort()
ans = ['/']
for f in folder:
if not is_sub(ans[-1].split('/'), f.split('/')):
ans.append(f)
return ans[1:]
another way is to sort the folder and then check while inserting in the trie if the path already exists, it it exists return False else add the path to trie and return True
it improves both time and space
Im not gonna watch the video until I attempt it myself ;) but I just came to check if you uploaded it and god damn! haha Neetcode is on top of it!
it's like a daily routine to me at this point 🥱
This kid probably looked up solution instead then solved it
Thanks for the great explanation for both approaches! One thing I could suggest for improving the Trie approach is after creating the the full Trie structure, dfs through it with an accumulating path array, and each time a node is found where end_of_folder is true, push the current path (as a string) to a result list, and then backtrack. That way you could potentially cut down on repeated work from that prefix_search method.
Thank you for the daily
I was able to use a Trie and perform pruning as I was adding folderPaths to the Trie.
You can find if a dir is subdir when adding to the Trie and break out of it. In the end just add all the strings in the trie.
thank you
8:33 how does hashlook up take time l
Very easy solution
23ms
Beats95.00%
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
# Sort folders lexicographically
folder.sort()
result = []
for f in folder:
# Check if f is a sub-folder of the last added folder
if not result or not f.startswith(result[-1] + '/'):
result.append(f)
return result
Exactly what I thought because of how the prefixes work.
class Solution {
public:
bool substr(string st1, string st2) {
if(st1.length() > st2.length()) return false;
for(int i = 0; i < st1.length(); i++) {
if(st1[i] != st2[i]) return false;
}
if(st2.size() > st1.size() && st2[st1.size()] != '/') return false;
return true;
}
vector removeSubfolders(vector& folder) {
sort(folder.begin(), folder.end());
vector sol;
if(folder.empty()) return sol;
for(int i = 0; i < folder.size()-1; i++) {
int j = i;
while(i < folder.size()-1 && substr(folder[j], folder[i+1])) {
i++;
}
sol.push_back(folder[j]);
}
if(sol.empty() || !substr(sol.back(), folder.back())) {
sol.push_back(folder.back());
}
return sol;
}
};
so i did this which beat 95% in c++
Simple Hashmap solution :
var removeSubfolders = function (folder) {
let output = []
let map = {}
for (let i = 0; i < folder.length; i++) {
map[folder[i]] = true
}
for (let i = 0; i < folder.length; i++) {
let eachFolder = folder[i].split("/").slice(1)
let subFolder = ""
let count = 0
for (let k = 0; k < eachFolder.length; k++) {
subFolder += '/' + eachFolder[k]
if (map[subFolder]) {
count++
}
}
if (count == 1) {
output.push(folder[i])
}
}
return output
};
Probably the worst designed problem, the description is of an alternate universe's logic.
Bro is speed
Let’s see how many people end up wiping their filesystems down to root after this 😂
how come u do it so fast!!!
Tomorrow: Split a String Into the Max Number of Unique Substrings
10/26: The Knight’s Tour
10/27: Minimum Number of Removals to Make Mountain Array
10/28: Count Square Submatrices with All Ones
10/29: Height of Binary Tree After Subtree Removal Queries
@@akialter all right I guess it's not sorcery. would u mind sharing the trick??
@@mrf92 check the leetcode calendar - shows all upcoming problems
@@committedeel1751 Is the calendar located under the "Problems" tab?
@@akialter Tomorrow: Split a String Into the Max Number of Unique Substrings . we already had this question 4 days ago as daily question
first!!!!!!
my comment not being first is a cool lesson in the eventual consistency of the youtube comment system ¯\_(ツ)_/¯
r u dropping hints, will that dismantle the botnet finally? i've been overindulging obliviousness bc my vagus nerve is 1 mm from rupturing, 22 yr old me would've boiled my laptop in risen and other chemicals needed to boil laptops.
also cool algorithm video or whatever, very smart.
- 4 year old desperately in need of being spoken to like a 4 year old