You are asked to design a file system that allows you to create new paths and associate them with different values.
The format of a path is one or more concatenated strings of the form: /
followed by one or more lowercase English letters. For example, “/leetcode"
and “/leetcode/problems" are valid paths while an empty string "" and
"/" are not.
Implement the FileSystem class:
bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn ’t exist.
int get(string path) Returns the value associated with path or returns -1 if the path doesn’t exist.
A file system can be modeled as a tree (trie), where each node represents a directory or file. Each path is split by ‘/’, and we traverse or create nodes accordingly. We only allow creating a path if its parent exists and the path does not already exist.
Use a trie node class with a dictionary for children and an integer for value (default -1 for non-existent).
For createPath, split the path by ‘/’, traverse the trie, and check if the parent exists and the path does not exist. If valid, create the node and set its value.
For get, traverse the trie by splitting the path and return the value if the node exists, else return -1.
Edge cases: root (’/’) is not a valid path to create or get.
classFileSystem {
classNode {
val ch = mutableMapOf<String, Node>()
var val_ = -1 }
privateval root = Node()
funcreatePath(path: String, value: Int): Boolean {
val parts = path.split("/").filter { it.isNotEmpty() }
var v = root
for (i in0 until parts.size - 1) {
v = v.ch[parts[i]] ?:returnfalse }
val last = parts.last()
if (v.ch.containsKey(last)) returnfalse v.ch[last] = Node().apply { val_ = value }
returntrue }
funget(path: String): Int {
val parts = path.split("/").filter { it.isNotEmpty() }
var v = root
for (p in parts) {
v = v.ch[p] ?:return -1 }
return v.val_
}
}
classFileSystem:
classNode:
def__init__(self):
self.ch = {}
self.val =-1def__init__(self):
self.root = self.Node()
defcreatePath(self, path: str, value: int) -> bool:
parts = [p for p in path.split('/') if p]
v = self.root
for i in range(len(parts)-1):
if parts[i] notin v.ch:
returnFalse v = v.ch[parts[i]]
last = parts[-1]
if last in v.ch:
returnFalse v.ch[last] = self.Node()
v.ch[last].val = value
returnTruedefget(self, path: str) -> int:
parts = [p for p in path.split('/') if p]
v = self.root
for p in parts:
if p notin v.ch:
return-1 v = v.ch[p]
return v.val