Search⌘ K

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

true
true
true
true
false

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

true
true
true
false
true
true
true

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 ...