Subdirectory Deletion
Solve a medium-level problem of deleting subdirectories in a file system using tries.
Problem statement
Given a list of strings representing directory structures of a file system, delete all the subdirectories of the path mentioned in the list and return the list of directories that are left after the deletions.
Example 1
Sample input
directories: ["/home/user", "/home/user/mike", "/system/code", "/home"]
Sample output
["/system/code", "/home"]
Explanation
mike is the sub-directory of /home/user, so it is deleted.
There are no sub-directories for /home/user/mike, so nothing is deleted.
There are no sub-directories for /system/code, so nothing is deleted./user is the sub-directory for home, so it is deleted.
Example 2
Sample input
directories: ["/home/user/mike", "/home/user/will", "/home/user/ben"]
Sample output
["/home/user/mike","/home/user/will","/home/user/ben"]
Explanation
There are no sub-directories for /home/user/mike, so nothing is deleted.
There are no sub-directories for /home/user/will, so nothing is deleted.
There are no sub-directories for /home/user/ben, so nothing is deleted.
Try it yourself
Try to solve the problem yourself before reading the solution.
#include <iostream>#include <vector>using namespace std;vector<string> deleteSubDir(vector<string> directories){// your code goes herevector<string> answer;return answer;}
Intuition
Let's try to understand the problem better. We're given directory paths, and we need to delete the subdirectories under them. Since we do not know which directory exists at the start, we keep creating the directories. For example, /home/user requires us to delete all the subdirectories under this path, which means all the subfolders present under the user folder. But it also gives us the information to create the directory /home/user. Once we've inserted all the directory paths into a trie, we can better visualize the file structure and delete all the subdirectories by reiterating the trie.
First, we must insert all the directories in the trie and later perform the subdirectory deletion. Another critical observation here is that if we've already inserted a directory in the trie, it does not make sense to insert its subdirectory in the trie because it will eventually be deleted. For example, if a directory /home/ben is already present in the trie, inserting home/ben/movies in the trie would be useless, as the movies folder will be deleted as a part of subdirectory deletion process.
To handle such cases, we introduce a new parameter in the trie node isEndOfPath. While inserting a directory in the trie, if we encounter isEndOfPath as true for any node, we terminate the insertion process.
Algorithm
The summary of the algorithm is given below.
Step 1: Insert all directories in the trie ...