Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1166.html
1166. Design File System
Level
Medium
Description
You are asked to design a file system which provides two functions:
- createPath(path, value): Creates a new path and associates a value to it if possible and returns
True
. ReturnsFalse
if the path already exists or its parent path doesn’t exist. - get(path): Returns the value associated with a path or returns
-1
if the path doesn’t exist.
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 two functions.
Please refer to the examples for clarifications.
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:
- The number of calls to the two functions is less than or equal to
10^4
in total. 2 <= path.length <= 100
1 <= value <= 10^9
Solution
Create a class TreeNode
that contains String path
, int value
and List<TreeNode> children
. The objects of TreeNode
are comparable using path
, and all the elements in children
are sorted in ascending order.
In class FileSystem
, maintain a list of roots, which are of type TreeNode
.
For the constructor, initialize the list of roots.
For createPath(path, value)
, remove the first /
and split path
into an array using /
. For each element in the array, try to find the corresponding node. If a node in the middle is not found, then the node in the parent path does not exist, so return false
. If a node at the last level is found, then the complete path already exists, so return false
. When the end of the path is reached, create a new node using the path and the value, and a child node is added to its parent’s children
.
For get(path)
, the logic is similar to createPath
. At any step, the path must be available, or return -1 otherwise. After the end of the path is reached, obtain the value and return.
-
class FileSystem { List<TreeNode> roots; public FileSystem() { roots = new ArrayList<TreeNode>(); } public boolean createPath(String path, int value) { if (path.charAt(0) == '/') path = path.substring(1); String[] array = path.split("/"); int length = array.length; TreeNode tempNode = null; List<TreeNode> tempList = roots; for (int i = 0; i < length; i++) { String subPath = array[i]; int index = binarySearch(tempList, subPath); if (index < 0 && i < length - 1 || index >= 0 && i == length - 1) return false; if (index >= 0) { tempNode = tempList.get(index); tempList = tempNode.getChildren(); } else { TreeNode newNode = new TreeNode(subPath, value); if (tempNode == null) { roots.add(newNode); Collections.sort(roots); } else tempNode.addChild(newNode); } } return true; } public int get(String path) { if (path.charAt(0) == '/') path = path.substring(1); String[] array = path.split("/"); int length = array.length; TreeNode tempNode = null; List<TreeNode> tempList = roots; for (int i = 0; i < length; i++) { String subPath = array[i]; int index = binarySearch(tempList, subPath); if (index < 0) return -1; else { tempNode = tempList.get(index); tempList = tempNode.getChildren(); } } return tempNode.getValue(); } public int binarySearch(List<TreeNode> list, String subPath) { int low = 0, high = list.size() - 1; while (low <= high) { int mid = (high - low) / 2 + low; TreeNode temp = list.get(mid); String tempPath = temp.getPath(); if (tempPath.compareTo(subPath) == 0) return mid; else if (tempPath.compareTo(subPath) < 0) low = mid + 1; else high = mid - 1; } return -low - 1; } } class TreeNode implements Comparable<TreeNode> { private String path; private int value; private List<TreeNode> children; public TreeNode() { children = new ArrayList<TreeNode>(); } public TreeNode(String path, int value) { this.path = path; this.value = value; children = new ArrayList<TreeNode>(); } public String getPath() { return path; } public int getValue() { return value; } public List<TreeNode> getChildren() { return children; } public void addChild(TreeNode child) { children.add(child); Collections.sort(children); } public int compareTo(TreeNode node) { return this.path.compareTo(node.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 { Map<String, Trie> children = new HashMap<>(); int v; boolean insert(String w, int v) { Trie node = this; String[] ps = w.split("/"); for (int i = 1; i < ps.length - 1; ++i) { String 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()); node = node.children.get(ps[ps.length - 1]); node.v = v; return true; } int search(String w) { Trie node = this; String[] ps = w.split("/"); for (int i = 1; i < ps.length; ++i) { String p = ps[i]; if (!node.children.containsKey(p)) { return -1; } node = node.children.get(p); } return node.v == 0 ? -1 : node.v; } } class FileSystem { private Trie trie = new Trie(); 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); */
-
// OJ: https://leetcode.com/problems/design-file-system/ // Time: // FileSystem: O(1) // createPath, get: O(P) // Space: O(N) class FileSystem { unordered_map<string, int> m; public: FileSystem() {} bool createPath(string path, int value) { if (m.count(path)) return false; auto i = path.find_last_of("/"); auto parent = path.substr(0, i); if (parent.size() && m.count(parent) == 0) return false; m[path] = value; return true; } int get(string path) { return m.count(path) ? m[path] : -1; } };
-
class Trie: def __init__(self): self.children = {} self.v = 0 def insert(self, w, v): 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() node = node.children[ps[-1]] node.v = v return True def search(self, w): node = self for p in w.split('/')[1:]: if p not in node.children: return -1 node = node.children[p] return node.v or -1 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)
-
type Trie struct { children map[string]*Trie v int } func newTrie() *Trie { m := map[string]*Trie{} return &Trie{children: m} } func (this *Trie) insert(w string, v int) bool { node := this ps := strings.Split(w, "/") for _, p := range ps[1 : len(ps)-1] { if _, ok := node.children[p]; !ok { return false } node, _ = node.children[p] } x := ps[len(ps)-1] if _, ok := node.children[x]; ok { return false } node.children[x] = newTrie() node, _ = node.children[x] node.v = v return true } func (this *Trie) search(w string) int { node := this for _, p := range strings.Split(w, "/")[1:] { if _, ok := node.children[p]; !ok { return -1 } node, _ = node.children[p] } if node.v == 0 { return -1 } return node.v } type FileSystem struct { trie *Trie } func Constructor() FileSystem { return FileSystem{newTrie()} } 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) */