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. Returns False 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)
     */
    
    

All Problems

All Solutions