Design In-Memory File System Python Solution

Tested Python solution for LeetCode 588 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 588, Hard. Topics: Design, Trie, Hash Table, String. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 588   # by problem number
lcpy gen -s design_in_memory_file_system   # by problem name

​

Problem

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.

​

Examples

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"]

​

Constraints

• 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

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class FileSystem:
    # Time: O(1)
    # Space: O(1)
    def __init__(self) -> None:
        self.files: dict[str, str] = {}  # path -> content
        self.dirs: set[str] = set()  # set of directory paths

    # Time: O(N + M + K log K) where N = files, M = dirs, K = items in result
    # Space: O(K) for result set and sorting
    def ls(self, path: str) -> list[str]:
        if path in self.files:
            return [path.split("/")[-1]]

        items = set()
        prefix = path + "/" if path != "/" else "/"

        for file_path in self.files:
            if file_path.startswith(prefix):
                remaining = file_path[len(prefix) :]
                if remaining and "/" not in remaining:
                    items.add(remaining)
                elif remaining and "/" in remaining:
                    items.add(remaining.split("/")[0])

        for dir_path in self.dirs:
            if dir_path.startswith(prefix):
                remaining = dir_path[len(prefix) :]
                if remaining and "/" not in remaining:
                    items.add(remaining)
                elif remaining and "/" in remaining:
                    items.add(remaining.split("/")[0])

        return sorted(items)

    # Time: O(D) where D = depth of path
    # Space: O(D) for path parts and directory storage
    def mkdir(self, path: str) -> None:
        parts = path.split("/")
        for i in range(1, len(parts) + 1):
            dir_path = "/".join(parts[:i])
            if dir_path:
                self.dirs.add(dir_path)

    # Time: O(D + C) where D = depth of path, C = content length
    # Space: O(D + C) for path parts and content storage
    def add_content_to_file(self, file_path: str, content: str) -> None:
        parts = file_path.split("/")
        for i in range(1, len(parts)):
            dir_path = "/".join(parts[:i])
            if dir_path:
                self.dirs.add(dir_path)

        self.files[file_path] = self.files.get(file_path, "") + content

    # Time: O(1)
    # Space: O(1)
    def read_content_from_file(self, file_path: str) -> str:
        return self.files.get(file_path, "")

​

Complexity

Time	Space
O(1)	O(1)

​

Tags

Grind, NeetCode All.