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:

Image text

Note:

  1. 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 "/".
  2. 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.
  3. 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);
     */
    

All Problems

All Solutions