Path Existence
Explore how to implement directory path insertion and existence checks using trie data structures. Learn to represent file systems with tries, enhancing folder management and retrieval by understanding folder-level traversal and time complexities.
Problem statement
Implement two methods, directoryInsert and directoryExists, for provided directory paths.
The directoryInsert method takes the directory path as the input to create the given path. It returns true if a new folder is created; else, it returns false.
The directoryExists method returns true or false depending on whether the provided directory exists in the system.
Example 1
Sample input
directoryInsert("/home/ben/files/movies")directoryInsert("/home/mike/profile")directoryExists("/home/ben/files")directoryInsert("/home/arnold/profile")directoryExists("/home/arnold/files")
Sample output
truetruetruetruefalse
Explanation
directoryInsert("/home/ben/files/movies") => Adds "home/ben/files/movies" to the file system. Since new folders "home", "ben","files" and "movies" were created, true is returned.directoryInsert("/home/mike/profile") => Adds "home/mike/profile" to the file system. Since new folders "mike" and "profile" were created, true is returned. directoryExists("/home/ben/files") => "home/ben/files" exists in the file system, so true is returned. directoryInsert("/home/arnold/profile") => Adds "home/arnold/profile" to the file system. Since new folders "arnold" and "profile" were created, true is returned. directoryExists("/home/arnold/files") => "home/arnold/files" does not exist in the file system, so false is returned.
Example 2
Sample input
directoryInsert("/a/b/c/d")directoryInsert("/a/e/g")directoryInsert("/h/b/f")directoryExists("/h/e")directoryInsert("/h/a/p")directoryExists("/a/e")directoryExists("/h/a/p")
Sample output
truetruetruefalsetruetruetrue
Explanation
directoryInsert("/a/b/c/d") => Adds the directory "a/b/c/d" to the file system.directoryInsert("/a/e/g") => Adds the directory "a/e/g" to the file system.directoryInsert("/h/b/f") => Adds the directory "h/b/f" to the file system.directoryExists("/h/e") => Directory "h/e" does not exist in the file system, so false is returned.directoryInsert("/h/a/p") => Adds the directory "h/a/p" to the file system.directoryExists("/a/e") => Directory "/a/e" exists in the file system, so true is returned.directoryExists("/h/a/p") => Directory "h/a/p" exists in the file system, so true is returned.
Try it yourself
Try to solve the problem ...