Design a file system that allows us to create new paths and associate them with different values. A path has one or more concatenated strings of the form / followed by one or more lowercase English letters. For example, valid paths include "/educative" and "/educative/problems", while an empty string "" and "/" are not valid paths.

Implement the FileSystem class with the following functions:

• bool createPath(string path, int value): This function creates a new path, associates a value to it if possible, and returns TRUE. It returns FALSE if the path already exists or its parent path doesn’t exist.

• int get(string path): This function returns the value associated with the path or returns -$1$ if the path doesn’t exist.

Constraints:

• The total number of calls to the two functions are $\leq$ $10^3$.

• $2 \leq$ path.length $\leq 100$

• $1 \leq$ value $\leq 10^9$

A file system is a tree-like structure where directories and files are nodes, and paths define their relationships. This structure inherently has a hierarchical, prefix-based nature. We can use a trie to replicate this hierarchy in our file system. Let’s explore a couple of use cases where using a trie is advantageous:

• When creating or searching for a path, we must validate the entire path step by step, ensuring each directory exists before adding or retrieving the next component. A Trie naturally supports this step-by-step validation as we traverse through its nodes.

• Many files and directories may share common prefixes, such as /a/b/c and /a/b/d. When creating such paths, a trie stores these common prefixes only once. For instance, the prefix /a/b/ is stored a single time, with different branches handling the unique parts (e.g., c and d). This approach reduces redundancy and conserves memory. Additionally, when searching for any path, each node in the trie represents a part of the path (a directory or file name), and the full path is formed by traversing from the root to the desired node.

Let’s look at how to implement the file system:

• First, create the TrieNode class that represents a node in the trie. It has the following variables:

  • map: A dictionary to store child nodes (directories or files)

  • name: The name of this node (e.g., a directory or file name)

  • value: The value stored at this node (used only for files, not directories)

• Next, create the FileSystem class that has the following methods:

  • Constructor: It initializes a new FileSystem instance by creating a root node (TrieNode). The root is initialized to an empty string representing the current state of the file system's root.

  • create_path(path, value): It creates a new path with a specified value. The following steps are involved:

    • Splits the path into parts or components by using / as the separator. For example, /a/b/c is divided into [" ", "a", "b", "c"].

    • Starts at the root node and traverses through each component. The root node is an empty node representing the start of all paths. For each other component:

      • If the current component is not the last:

        • If it doesn't exist in the current node's map, it means the required parent directory is missing, so the function returns FALSE.

        • If it exists, move to this node.

      • If the current component is the last:

        • If it doesn't exist in the current node's map, create a new TrieNode.

        • If it exists and has a value, it means an overwriting of the existing data is required, so the function returns FALSE.

    • If the path is valid (created successfully) and the last node doesn’t have a value, assign the given value to this node, and return TRUE. Otherwise, return FALSE.

  • get(path): It retrieves the value stored at the specified path. The following steps are involved:

    • Splits the path into parts or components by using / as the separator.

    • Starts at the root node and traverses through each component.

      • If a component is missing at any point, return $-1$ representing path not found.

      • Return that value if all components are found and the last node has a value.

Let’s look at the following illustration to get a better understanding of the solution: