Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/588.html
588. Design In-Memory File System
Level
Hard
Description
Design an in-memory file system to simulate the following functions:
ls
: Given a path in string format. If it is a file path, return a list that only contains this file’s name. If it is a directory path, return the list of file and directory names in this directory. Your output (file and directory names together) should in lexicographic order.
mkdir
: Given a directory path that does not exist, you should make a new directory according to the path. If the middle directories in the path don’t exist either, you should create them as well. This function has void return type.
addContentToFile
: Given a file path and file content in string format. If the file doesn’t exist, you need to create that file containing given content. If the file already exists, you need to append given content to original content. This function has void return type.
readContentFromFile
: Given a file path, return its content in string format.
Example:
Input:
[“FileSystem”,”ls”,”mkdir”,”addContentToFile”,”ls”,”readContentFromFile”] [[],[”/”],[“/a/b/c”],[“/a/b/c/d”,”hello”],[”/”],[“/a/b/c/d”]]
Output:
[null,[],null,null,[“a”],”hello”]
Explanation:
Note:
- You can assume all file or directory paths are absolute paths which begin with
/
and do not end with/
except that the path is just"/"
. - You can assume that all operations will be passed valid parameters and users will not attempt to retrieve file content or list a directory or file that does not exist.
- You can assume that all directory names and file names only contain lower-case letters, and same names won’t exist in the same directory.
Solution
Define a class Node
. Each object of Node
has a data field String path
, a data field boolean isFile
, and a data field List<Node> children
. In FileSystem
class, create a root of type Node
. Besides, create a map that stores each file path with its corresponding content.
For the constructor, initialize the root and the map.
For method ls
, find the node at the end of the path, and obtain the node’s children. If the node is a file, then use a list to store the file’s name and return the list. Otherwise, use a list to store the children’s paths and return the list.
For method mkdir
, find all the nodes in the given path, and create the nodes if they do not exist.
For method addContentToFile
, like mkdir
, find all the nodes in the given path and create the nodes if they do not exist. For the last node which is the file, create the file using isFile = true
. Then obtain the content of the file if it already exists, or an empty string otherwise, append the new content to the content, and update the file path with the updated content.
For method readContentFromFile
, simply obtain the content from the map using the file path and return the content.
-
class FileSystem { Node root; Map<String, String> fileContentMap; public FileSystem() { root = new Node(); fileContentMap = new HashMap<String, String>(); } public List<String> ls(String path) { String[] array = path.substring(1).split("/"); Node node = root; int length = path.length() == 1 ? 0 : array.length; for (int i = 0; i < length; i++) { String subPath = array[i]; int index = binarySearch(node.children, subPath); if (index >= 0) node = node.children.get(index); else return new ArrayList<String>(); } List<String> list = new ArrayList<String>(); if (node.isFile) { String nodePath = node.path; list.add(node.path); } else { List<Node> children = node.children; int size = children.size(); for (int i = 0; i < size; i++) { Node child = children.get(i); list.add(child.path); } } return list; } public void mkdir(String path) { if (path.equals("/")) return; String[] array = path.substring(1).split("/"); Node node = root; int length = array.length; for (int i = 0; i < length; i++) { String subPath = array[i]; int index = binarySearch(node.children, subPath); if (index >= 0) node = node.children.get(index); else { Node newNode = new Node(subPath, false); node.children.add(-index - 1, newNode); node = newNode; } } } public void addContentToFile(String filePath, String content) { String[] array = filePath.substring(1).split("/"); Node node = root; int length = array.length - 1; for (int i = 0; i < length; i++) { String subPath = array[i]; int index = binarySearch(node.children, subPath); if (index >= 0) node = node.children.get(index); else { Node newNode = new Node(subPath, false); node.children.add(-index - 1, newNode); node = newNode; } } Node fileNode = new Node(array[length], true); int index = binarySearch(node.children, array[length]); if (index < 0) node.children.add(-index - 1, fileNode); String prevContent = fileContentMap.getOrDefault(filePath, ""); String newContent = prevContent + content; fileContentMap.put(filePath, newContent); } public String readContentFromFile(String filePath) { return fileContentMap.getOrDefault(filePath, ""); } private int binarySearch(List<Node> list, String key) { int low = 0, high = list.size() - 1; while (low <= high) { int mid = (high - low) / 2 + low; Node node = list.get(mid); if (node.path.equals(key)) return mid; else if (node.path.compareTo(key) > 0) high = mid - 1; else low = mid + 1; } return -low - 1; } } class Node { String path; boolean isFile; List<Node> children; public Node() { this("", false); } public Node(String path, boolean isFile) { this.path = path; this.isFile = isFile; if (!isFile) children = new ArrayList<Node>(); } } /** * Your FileSystem object will be instantiated and called as such: * FileSystem obj = new FileSystem(); * List<String> param_1 = obj.ls(path); * obj.mkdir(path); * obj.addContentToFile(filePath,content); * String param_4 = obj.readContentFromFile(filePath); */ ############ class Trie { String name; boolean isFile; StringBuilder content = new StringBuilder(); Map<String, Trie> children = new HashMap<>(); Trie insert(String path, boolean isFile) { Trie node = this; String[] ps = path.split("/"); for (int i = 1; i < ps.length; ++i) { String p = ps[i]; if (!node.children.containsKey(p)) { node.children.put(p, new Trie()); } node = node.children.get(p); } node.isFile = isFile; if (isFile) { node.name = ps[ps.length - 1]; } return node; } Trie search(String path) { Trie node = this; String[] ps = path.split("/"); for (int i = 1; i < ps.length; ++i) { String p = ps[i]; if (!node.children.containsKey(p)) { return null; } node = node.children.get(p); } return node; } } class FileSystem { private Trie root = new Trie(); public FileSystem() { } public List<String> ls(String path) { List<String> ans = new ArrayList<>(); Trie node = root.search(path); if (node == null) { return ans; } if (node.isFile) { ans.add(node.name); return ans; } for (String v : node.children.keySet()) { ans.add(v); } Collections.sort(ans); return ans; } public void mkdir(String path) { root.insert(path, false); } public void addContentToFile(String filePath, String content) { Trie node = root.insert(filePath, true); node.content.append(content); } public String readContentFromFile(String filePath) { Trie node = root.search(filePath); return node.content.toString(); } } /** * Your FileSystem object will be instantiated and called as such: * FileSystem obj = new FileSystem(); * List<String> param_1 = obj.ls(path); * obj.mkdir(path); * obj.addContentToFile(filePath,content); * String param_4 = obj.readContentFromFile(filePath); */
-
// OJ: https://leetcode.com/problems/design-in-memory-file-system/ struct File { bool isDirectory = true; map<string, File*> contents; string name, content; File(string name) : name(name) {} }; class FileSystem { File root = File(""); File *getFile(string path, bool createFile = false) { istringstream ss(path); string name; auto fp = &root; getline(ss, name, '/'); while (getline(ss, name, '/')) { if (fp->contents.count(name) == 0) { fp->contents[name] = new File(name); } fp = fp->contents[name]; } if (createFile) fp->isDirectory = false; return fp; } public: FileSystem() {} vector<string> ls(string path) { auto fp = getFile(path); if (fp->isDirectory) { vector<string> ans; for (auto &[name, fp] : fp->contents) { ans.push_back(name); } return ans; } return { fp->name }; } void mkdir(string path) { getFile(path); } void addContentToFile(string filePath, string content) { getFile(filePath, true)->content += content; } string readContentFromFile(string filePath) { return getFile(filePath)->content; } };
-
class Trie: def __init__(self): self.name = None self.isFile = False self.content = [] self.children = {} def insert(self, path, isFile): node = self ps = path.split('/') for p in ps[1:]: if p not in node.children: node.children[p] = Trie() node = node.children[p] node.isFile = isFile if isFile: node.name = ps[-1] return node def search(self, path): node = self if path == '/': return node ps = path.split('/') for p in ps[1:]: if p not in node.children: return None node = node.children[p] return node class FileSystem: def __init__(self): self.root = Trie() def ls(self, path: str) -> List[str]: node = self.root.search(path) if node is None: return [] if node.isFile: return [node.name] return sorted(node.children.keys()) def mkdir(self, path: str) -> None: self.root.insert(path, False) def addContentToFile(self, filePath: str, content: str) -> None: node = self.root.insert(filePath, True) node.content.append(content) def readContentFromFile(self, filePath: str) -> str: node = self.root.search(filePath) return ''.join(node.content) # Your FileSystem object will be instantiated and called as such: # obj = FileSystem() # param_1 = obj.ls(path) # obj.mkdir(path) # obj.addContentToFile(filePath,content) # param_4 = obj.readContentFromFile(filePath) ############ class FileNode(object): def __init__(self, name): self.isFolder = True self.childs = {} self.name = name self.data = "" def appendData(self, data): self.data += data def readAll(self): return self.data class FileSystem(object): def __init__(self): self.root = FileNode("/") def ls(self, path): """ :type path: str :rtype: List[str] """ fd = self.lookup(path, False) if not fd: return [] if not fd.isFolder: return [fd.name] files = [] for file in fd.childs: files.append(file) files.sort() return files def lookup(self, path, isAutoCreate): path = path.split("/") p = self.root for name in path: if not name: continue if name not in p.childs: if isAutoCreate: p.childs[name] = FileNode(name) else: return None p = p.childs[name] return p def mkdir(self, path): """ :type path: str :rtype: void """ self.lookup(path, True) def addContentToFile(self, filePath, content): """ :type filePath: str :type content: str :rtype: void """ fd = self.lookup(filePath, True) fd.isFolder = False fd.appendData(content) def readContentFromFile(self, filePath): """ :type filePath: str :rtype: str """ fd = self.lookup(filePath, False) if fd: return fd.readAll() return "" # Your FileSystem object will be instantiated and called as such: # obj = FileSystem() # param_1 = obj.ls(path) # obj.mkdir(path) # obj.addContentToFile(filePath,content) # param_4 = obj.readContentFromFile(filePath)
-
type Trie struct { name string isFile bool content strings.Builder children map[string]*Trie } func newTrie() *Trie { m := map[string]*Trie{} return &Trie{children: m} } func (this *Trie) insert(path string, isFile bool) *Trie { node := this ps := strings.Split(path, "/") for _, p := range ps[1:] { if _, ok := node.children[p]; !ok { node.children[p] = newTrie() } node, _ = node.children[p] } node.isFile = isFile if isFile { node.name = ps[len(ps)-1] } return node } func (this *Trie) search(path string) *Trie { if path == "/" { return this } node := this ps := strings.Split(path, "/") for _, p := range ps[1:] { if _, ok := node.children[p]; !ok { return nil } node, _ = node.children[p] } return node } type FileSystem struct { root *Trie } func Constructor() FileSystem { root := newTrie() return FileSystem{root} } func (this *FileSystem) Ls(path string) []string { var ans []string node := this.root.search(path) if node == nil { return ans } if node.isFile { ans = append(ans, node.name) return ans } for v := range node.children { ans = append(ans, v) } sort.Strings(ans) return ans } func (this *FileSystem) Mkdir(path string) { this.root.insert(path, false) } func (this *FileSystem) AddContentToFile(filePath string, content string) { node := this.root.insert(filePath, true) node.content.WriteString(content) } func (this *FileSystem) ReadContentFromFile(filePath string) string { node := this.root.search(filePath) return node.content.String() } /** * Your FileSystem object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Ls(path); * obj.Mkdir(path); * obj.AddContentToFile(filePath,content); * param_4 := obj.ReadContentFromFile(filePath); */