Leetcode: 588. Design In-Memory File System

Problem Statement

Understand the problem

Given a list of path where some are directories and other are files. Implement an efficient data structure that allows easily access to each directory to save files and list its content.

Devise a plan

Use Trie to represent the directory and file paths. Time complexity is \(O(p)\) to find a node (for mkdir, write and read) where \(p\) is the length of the path, \(O(p + P)\) for ls where the \(P\) is the sum of length of all nodes in a sub-path.

Carry out the plan

class FileSystem:

    def __init__(self):
        self.root = {}

    def ls(self, path: str) -> List[str]:
        node = self.node(path)
        if "__content__" in node:
            return [path.split("/")[-1]]
        return list(sorted(node.keys()))

    def mkdir(self, path: str) -> None:
        self.node(path)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.node(filePath)
        node["__content__"] = node.get("__content__", "") + content

    def readContentFromFile(self, filePath: str) -> str:
        return self.node(filePath).get("__content__", "")

    def node(self, path):
        if path == "/":
            return self.root
        node = self.root
        for p in path.split("/")[1:]:
            node = node.setdefault(p, {})
        return node


# 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)