| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1479 |
Biweekly Contest 7 Q2 |
|
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 newpathand associates avalueto it if possible and returnstrue. Returnsfalseif the path already exists or its parent path doesn't exist.int get(string path)Returns the value associated withpathor returns-1if the path doesn't exist.
Example 1:
Input:
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1
Example 2:
Input:
["FileSystem","createPath","createPath","get","createPath","get"]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
Output:
[null,true,true,2,false,-1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/leet", 1); // return true
fileSystem.createPath("/leet/code", 2); // return true
fileSystem.get("/leet/code"); // return 2
fileSystem.createPath("/c/d", 1); // return false because the parent path "/c" doesn't exist.
fileSystem.get("/c"); // return -1 because this path doesn't exist.
Constraints:
2 <= path.length <= 1001 <= value <= 109- Each
pathis valid and consists of lowercase English letters and'/'. - At most
104calls in total will be made tocreatePathandget.
We can use a trie to store the paths, where each node stores a value, representing the value of the path corresponding to the node.
The structure of the trie node is defined as follows:
children: Child nodes, stored in a hash table, where the key is the path of the child node, and the value is the reference to the child node.v: The value of the path corresponding to the current node.
The methods of the trie are defined as follows:
-
insert(w, v): Insert the path$w$ and set its corresponding value to$v$ . If the path$w$ already exists or its parent path does not exist, returnfalse, otherwise returntrue. The time complexity is$O(|w|)$ , where$|w|$ is the length of the path$w$ . -
search(w): Return the value corresponding to the path$w$ . If the path$w$ does not exist, return$-1$ . The time complexity is$O(|w|)$ .
The total time complexity is
class Trie:
def __init__(self, v: int = -1):
self.children = {}
self.v = v
def insert(self, w: str, v: int) -> bool:
node = self
ps = w.split("/")
for p in ps[1:-1]:
if p not in node.children:
return False
node = node.children[p]
if ps[-1] in node.children:
return False
node.children[ps[-1]] = Trie(v)
return True
def search(self, w: str) -> int:
node = self
for p in w.split("/")[1:]:
if p not in node.children:
return -1
node = node.children[p]
return node.v
class FileSystem:
def __init__(self):
self.trie = Trie()
def createPath(self, path: str, value: int) -> bool:
return self.trie.insert(path, value)
def get(self, path: str) -> int:
return self.trie.search(path)
# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.createPath(path,value)
# param_2 = obj.get(path)class Trie {
Map<String, Trie> children = new HashMap<>();
int v;
Trie(int v) {
this.v = v;
}
boolean insert(String w, int v) {
Trie node = this;
var ps = w.split("/");
for (int i = 1; i < ps.length - 1; ++i) {
var p = ps[i];
if (!node.children.containsKey(p)) {
return false;
}
node = node.children.get(p);
}
if (node.children.containsKey(ps[ps.length - 1])) {
return false;
}
node.children.put(ps[ps.length - 1], new Trie(v));
return true;
}
int search(String w) {
Trie node = this;
var ps = w.split("/");
for (int i = 1; i < ps.length; ++i) {
var p = ps[i];
if (!node.children.containsKey(p)) {
return -1;
}
node = node.children.get(p);
}
return node.v;
}
}
class FileSystem {
private Trie trie = new Trie(-1);
public FileSystem() {
}
public boolean createPath(String path, int value) {
return trie.insert(path, value);
}
public int get(String path) {
return trie.search(path);
}
}
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem obj = new FileSystem();
* boolean param_1 = obj.createPath(path,value);
* int param_2 = obj.get(path);
*/class Trie {
public:
unordered_map<string, Trie*> children;
int v;
Trie(int v) {
this->v = v;
}
bool insert(string& w, int v) {
Trie* node = this;
auto ps = split(w, '/');
for (int i = 1; i < ps.size() - 1; ++i) {
auto p = ps[i];
if (!node->children.count(p)) {
return false;
}
node = node->children[p];
}
if (node->children.count(ps.back())) {
return false;
}
node->children[ps.back()] = new Trie(v);
return true;
}
int search(string& w) {
Trie* node = this;
auto ps = split(w, '/');
for (int i = 1; i < ps.size(); ++i) {
auto p = ps[i];
if (!node->children.count(p)) {
return -1;
}
node = node->children[p];
}
return node->v;
}
private:
vector<string> split(string& s, char delim) {
stringstream ss(s);
string item;
vector<string> res;
while (getline(ss, item, delim)) {
res.emplace_back(item);
}
return res;
}
};
class FileSystem {
public:
FileSystem() {
trie = new Trie(-1);
}
bool createPath(string path, int value) {
return trie->insert(path, value);
}
int get(string path) {
return trie->search(path);
}
private:
Trie* trie;
};
/**
* Your FileSystem object will be instantiated and called as such:
* FileSystem* obj = new FileSystem();
* bool param_1 = obj->createPath(path,value);
* int param_2 = obj->get(path);
*/type trie struct {
children map[string]*trie
v int
}
func newTrie(v int) *trie {
return &trie{map[string]*trie{}, v}
}
func (t *trie) insert(w string, v int) bool {
node := t
ps := strings.Split(w, "/")
for _, p := range ps[1 : len(ps)-1] {
if _, ok := node.children[p]; !ok {
return false
}
node = node.children[p]
}
if _, ok := node.children[ps[len(ps)-1]]; ok {
return false
}
node.children[ps[len(ps)-1]] = newTrie(v)
return true
}
func (t *trie) search(w string) int {
node := t
ps := strings.Split(w, "/")
for _, p := range ps[1:] {
if _, ok := node.children[p]; !ok {
return -1
}
node = node.children[p]
}
return node.v
}
type FileSystem struct {
trie *trie
}
func Constructor() FileSystem {
return FileSystem{trie: newTrie(-1)}
}
func (this *FileSystem) CreatePath(path string, value int) bool {
return this.trie.insert(path, value)
}
func (this *FileSystem) Get(path string) int {
return this.trie.search(path)
}
/**
* Your FileSystem object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.CreatePath(path,value);
* param_2 := obj.Get(path);
*/class Trie {
children: Map<string, Trie>;
v: number;
constructor(v: number) {
this.children = new Map<string, Trie>();
this.v = v;
}
insert(w: string, v: number): boolean {
let node: Trie = this;
const ps = w.split('/').slice(1);
for (let i = 0; i < ps.length - 1; ++i) {
const p = ps[i];
if (!node.children.has(p)) {
return false;
}
node = node.children.get(p)!;
}
if (node.children.has(ps[ps.length - 1])) {
return false;
}
node.children.set(ps[ps.length - 1], new Trie(v));
return true;
}
search(w: string): number {
let node: Trie = this;
const ps = w.split('/').slice(1);
for (const p of ps) {
if (!node.children.has(p)) {
return -1;
}
node = node.children.get(p)!;
}
return node.v;
}
}
class FileSystem {
trie: Trie;
constructor() {
this.trie = new Trie(-1);
}
createPath(path: string, value: number): boolean {
return this.trie.insert(path, value);
}
get(path: string): number {
return this.trie.search(path);
}
}
/**
* Your FileSystem object will be instantiated and called as such:
* var obj = new FileSystem()
* var param_1 = obj.createPath(path,value)
* var param_2 = obj.get(path)
*/