//approach 1
class Solution {
public List<String> removeSubfolders(String[] folder) {
//sort on the basis of length
// by this way all the subfolders will always appear after their parent folders
//example: ["/ah/al/am","/ah/al"] after sorting ["/ah/al","/ah/al/am"]
Arrays.sort(folder,(a,b)->a.length()-b.length());
List<String> list = new ArrayList<>();
Trie t = new Trie();
for(String s : folder){
if(t.insert(s,t)){
list.add(s);
}
}
return list;
}
}
class Trie{
boolean end = false;
Map<String,Trie> map;
public Trie(){
map = new HashMap<>();
}
public boolean insert(String string, Trie root){
Trie temp = root;
String str[] = string.split("/");
int i =0;
for(String s : str){
if(s.equals("")) continue;
if(!temp.map.containsKey(s)){
temp.map.put(s,new Trie());
}
if(temp.end) return false;
temp = temp.map.get(s);
}
temp.end = true;
return true;
}
}
//approach 2
class Solution {
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder,(a,b)->a.length()-b.length());
List<String> list = new ArrayList<>();
Trie t = new Trie();
// add all the folders in trie
for(String s : folder){
t.insert(s,t);
}
// check which folders are subfolders and don't add them in the final result list
for(String s : folder){
if(t.canAdd(s,t)){
list.add(s);
}
}
return list;
}
}
class Trie{
boolean end = false;
Map<String,Trie> map;
public Trie(){
map = new HashMap<>();
}
//insert
public void insert(String string, Trie root){
Trie temp = root;
String str[] = string.split("/");
int i =0;
for(String s : str){
if(s.equals("")) continue;
if(!temp.map.containsKey(s)){
temp.map.put(s,new Trie());
}
temp = temp.map.get(s);
}
temp.end = true;
}
public boolean canAdd(String string, Trie root){
Trie temp = root;
String str[] = string.split("/");
int i =0;//keep counter
for(String s : str){
if(s.equals("")) continue;
if(!temp.map.containsKey(s)){
temp.map.put(s,new Trie());
}
//if i<str.length and temp.end = true it means that this must be a subfolder because it is
//present inside of a praent folder
//example : parent could be /abc
//subfolder could be (in this case) : /abc/pqr
//so we will get temp.end= true before we are finished with all the the string in str or subfolders
if(temp.end) return false;
temp = temp.map.get(s);
i++;
}
return true;
}
}
Top comments (0)