Leetcode 588. Design In-Memory File System

Problem

Design and implement an in-memory virtual file system that mimics basic file system operations. Your implementation should support creating directories, listing directory contents, creating files with content, appending to existing files, and reading file contents.

The file system starts with a root directory /. All paths are absolute paths beginning with /, and path components are separated by forward slashes. Your system must correctly distinguish between files (which contain data) and directories (which can contain other files or directories).

You need to implement the following operations:

• ls(path): If the path points to a file, return a list containing only that filename. If it points to a directory, return a list of all file and directory names in that directory, sorted in lexicographic order.
• mkdir(path): Create a directory at the given path. If any parent directories don't exist, create them automatically.
• add_content_to_file(file_path, content): If the file doesn't exist, create it with the given content. If it exists, append the content to the existing file content.
• read_content_from_file(file_path): Return the complete content of the file at the given path.

Requirements

1. Implement a tree-based structure to represent the hierarchical file system
2. Correctly differentiate between files and directories
3. Support automatic creation of intermediate directories when needed
4. Maintain lexicographic ordering when listing directory contents
5. Handle file content storage and retrieval efficiently
6. Parse paths correctly to navigate through the directory tree

Constraints

• Path length: 1 ≤ length ≤ 500
• All paths are valid absolute paths starting with /
• File and directory names contain only lowercase letters, digits, and dots
• Content string length: 0 ≤ length ≤ 10,000
• Total number of operations: ≤ 10,000
• Paths will not have trailing slashes (except root /)
• You can assume all inputs are valid (e.g., reading from existing files)

Examples

Example 1:

` Operations: fs = FileSystem() fs.mkdir("/home/user") fs.ls("/") fs.add_content_to_file("/home/user/file.txt", "Hello") fs.ls("/home/user") fs.read_content_from_file("/home/user/file.txt")

Output: ["home"] ["file.txt"] "Hello"

Explanation:

• Created /home/user directory (including parent /home)
• Listed root directory showing "home"
• Created file with content "Hello"
• Listed /home/user showing "file.txt"
• Read file content returning "Hello" `

Example 2:

` Operations: fs = FileSystem() fs.add_content_to_file("/app.log", "Error: ") fs.add_content_to_file("/app.log", "Connection failed") fs.read_content_from_file("/app.log") fs.ls("/app.log")

Output: "Error: Connection failed" ["app.log"]

Explanation:

• First add creates the file with "Error: "
• Second add appends "Connection failed"
• Reading returns concatenated content
• Listing a file path returns just that filename `

Example 3:

` Operations: fs = FileSystem() fs.mkdir("/var/log") fs.mkdir("/var/data") fs.add_content_to_file("/var/config.txt", "settings") fs.ls("/var")

Output: ["config.txt", "data", "log"]

Explanation: Directory listing includes both files and subdirectories in alphabetical order `

Hint 1: Data Structure Choice Consider using a tree or trie-like structure where each node represents either a file or a directory. Each directory node needs to store its children (subdirectories and files), while file nodes need to store content. A dictionary/map is perfect for storing children with names as keys.

Hint 2: Path Parsing Break the path into components by splitting on /. Skip empty strings (from leading or double slashes). Navigate through the tree by following each component. For mkdir and add_content operations, create missing intermediate nodes as directories on the fly.

Hint 3: File vs Directory Distinction The key insight is that a node becomes a file when content is added to it, and becomes/stays a directory when it has children. You can use a boolean flag or check if content exists to distinguish. When listing, if the path points to a file (has content), return just that filename; otherwise, return sorted children names.

Full Solution `` Approach Explanation:

The solution uses a tree structure where each node is a dictionary containing:

• children: A dictionary mapping child names to child nodes
• content: A string storing file content (empty for directories)

Key Design Decisions:

1. Node Structure: Each node can act as both a file or directory. A node with content is treated as a file; a node with children is a directory. This allows for flexible representation.
2. Path Navigation: The _navigate_to_node helper method parses paths by splitting on / and traversing the tree. It can optionally create missing intermediate directories.
3. File vs Directory Distinction: When listing, if a node has content, it's treated as a file and we return just its name. Otherwise, we return its sorted children.
4. Content Handling: File content is stored directly in the node and appended when additional content is added.

Time Complexity:

• ls(path): O(n + k log k) where n is the path depth and k is the number of children to sort
• mkdir(path): O(n) where n is the path depth
• add_content_to_file(path, content): O(n + m) where n is path depth and m is content length
• read_content_from_file(path): O(n + m) where n is path depth and m is content length

Space Complexity:

• O(T) where T is the total number of files and directories created, plus the total size of all file contents

class FileSystem:
    def __init__(self):
        # Root node of the file system tree
        # Each node is a dict with:
        # - 'children': dict mapping names to child nodes
        # - 'content': string content (empty for directories, non-empty for files)
        self.root = {'children': {}, 'content': ''}
    
    def _navigate_to_node(self, path: str, create_missing: bool = False):
        """
        Navigate to a node given a path.
        If create_missing is True, create intermediate directories.
        Returns the node and the final component name (or None for root).
        """
        if path == '/':
            return self.root, None
        
        # Split path and filter out empty strings
        components = [c for c in path.split('/') if c]
        
        current = self.root
        # Navigate to the parent of the final component
        for component in components[:-1]:
            if component not in current['children']:
                if create_missing:
                    current['children'][component] = {'children': {}, 'content': ''}
                else:
                    return None, None
            current = current['children'][component]
        
        return current, components[-1]
    
    def ls(self, path: str) -> list[str]:
        """
        List contents of a directory or return the filename if path is a file.
        """
        if path == '/':
            # List root directory
            return sorted(self.root['children'].keys())
        
        parent, name = self._navigate_to_node(path, create_missing=False)
        if parent is None or name not in parent['children']:
            return []
        
        node = parent['children'][name]
        
        # If it's a file (has content and no children, or we treat content presence as file)
        # Return just the filename
        if node['content']:
            return [name]
        
        # It's a directory, return sorted children
        return sorted(node['children'].keys())
    
    def mkdir(self, path: str) -> None:
        """
        Create a directory at the given path, creating intermediate directories as needed.
        """
        if path == '/':
            return  # Root already exists
        
        parent, name = self._navigate_to_node(path, create_missing=True)
        
        # Create the final directory if it doesn't exist
        if name not in parent['children']:
            parent['children'][name] = {'children': {}, 'content': ''}
    
    def add_content_to_file(self, file_path: str, content: str) -> None:
        """
        Add content to a file. Create the file if it doesn't exist.
        Append to existing content if the file exists.
        """
        parent, name = self._navigate_to_node(file_path, create_missing=True)
        
        # Create or update the file
        if name not in parent['children']:
            parent['children'][name] = {'children': {}, 'content': content}
        else:
            # Append to existing content
            parent['children'][name]['content'] += content
    
    def read_content_from_file(self, file_path: str) -> str:
        """
        Read and return the content of a file.
        """
        parent, name = self._navigate_to_node(file_path, create_missing=False)
        
        if parent and name in parent['children']:
            return parent['children'][name]['content']
        
        return ''