LeetCode 588: Design In-Memory File System Solution in Python – A Step-by-Step Guide

What Is LeetCode 588: Design In-Memory File System?

In LeetCode 588: Design In-Memory File System, you need to design a class FileSystem with four methods: ls(path) to list directory contents or a file name, mkdir(path) to create directories, addContentToFile(filePath, content) to add content to a file (creating it if it doesn’t exist), and readContentFromFile(filePath) to retrieve a file’s content. Paths are absolute (e.g., "/a/b/c"), and the system mimics a hierarchical file structure in memory. For example, after operations like mkdir("/a/b"), addContentToFile("/a/b/c.txt", "Hello"), calling ls("/a/b") returns ["c.txt"]. This problem builds on LeetCode 208: Implement Trie (Prefix Tree) for tree structures but extends to file system functionality.

Problem Statement

• Class: FileSystem
• Methods:
• ls(path: str) -> List[str]: List contents at path (sorted).
• mkdir(path: str): Create directory structure for path.
• addContentToFile(filePath: str, content: str): Add content to file at filePath.
• readContentFromFile(filePath: str) -> str: Return file content.
• Rules: Hierarchical paths; directories and files coexist; ls on file returns file name.

Constraints

• 1 <= path.length, filePath.length <= 100
• Paths start with '/' and contain lowercase English letters and '/'
• 1 <= content.length <= 100
• At most 100 calls to each method

Examples

• Input:
• ["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]
• [ [], ["/"], ["/a/b/c"], ["/a/b/c/d.txt","hello"], ["/a/b/c"], ["/a/b/c/d.txt"] ]
• Output:
• [null, [], null, null, ["d.txt"], "hello"]
• ls("/"): Empty root.
• mkdir("/a/b/c"): Creates path.
• addContentToFile("/a/b/c/d.txt","hello"): Adds file.
• ls("/a/b/c"): Lists "d.txt".
• readContentFromFile("/a/b/c/d.txt"): Returns "hello".

Understanding the Problem: Designing a File System

To solve LeetCode 588: Design In-Memory File System in Python, we need to design a data structure supporting hierarchical paths, directory listing, file creation, and content management, handling up to 100 operations efficiently. A brute-force flat dictionary storing full paths could work but struggles with directory traversal (O(n) per ls). Instead, a trie-based structure mimics a real file system, enabling O(m) operations (m = path length) by organizing nodes hierarchically. We’ll explore:

• Best Solution (Trie-Based Directory Structure): O(m) time per operation, O(n) space—fast and optimal (m = path length, n = total nodes).
• Alternative Solution (Flat Dictionary Approach): O(n) time for ls, O(n) space—simpler but slower for listing.

Let’s dive into the trie solution with a friendly breakdown!

Best Solution: Trie-Based Directory Structure

Why Trie Wins

The trie-based directory structure is the best for LeetCode 588 because it supports all operations in O(m) time and O(n) space by using a tree-like structure where each node represents a directory or file, efficiently handling path traversal, content storage, and sorted listing with a natural hierarchy. It’s like building a virtual file tree, branching out directories and hanging files where they belong—all in a swift, organized way!

How It Works

Think of this as a file-system architect:

• Step 1: Define Node Structure:
• Each node has children (dict of subdirectories/files) and content (string for files, empty for dirs).
• Step 2: Implement Methods:
• ls(path): Traverse to path, return sorted keys (dirs/files) or file name if path is a file.
• mkdir(path): Create nodes along path if they don’t exist.
• addContentToFile(filePath, content): Traverse to file, create if needed, append content.
• readContentFromFile(filePath): Traverse to file, return content.
• Step 3: Use Trie:
• Root node starts empty; paths split by '/' guide traversal.
• Why It Works:
• Trie mimics file system hierarchy.
• O(m) traversal per operation due to path length.

It’s like a file-system design maestro!

Step-by-Step Example

Example: Operations on FileSystem

• Init: Root node {children: {}, content: ""}.
• ls("/"):
• Root children = {}, return [].
• mkdir("/a/b/c"):
• Traverse/create: / → a → b → c.
• Tree: {children: {"a": {children: {"b": {children: {"c": {children: {}, content: ""}}}}}}}.
• addContentToFile("/a/b/c/d.txt", "hello"):
• Traverse/create: /a/b/c → d.txt, set content = "hello".
• Tree: {"c": {children: {"d.txt": {children: {}, content: "hello"}}}}.
• ls("/a/b/c"):
• At c, children = {"d.txt"}, return ["d.txt"].
• readContentFromFile("/a/b/c/d.txt"):
• At d.txt, return "hello".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class FileSystem:
    def __init__(self):
        # Root node with empty children and content
        self.root = {"children": {}, "content": ""}

    def ls(self, path: str) -> List[str]:
        # Traverse to path
        node = self.root
        if path != "/":
            parts = path.split("/")[1:]  # Skip leading "/"
            for part in parts:
                node = node["children"][part]

        # If file, return its name; else, return sorted children
        if node["content"]:
            return [path.split("/")[-1]]
        return sorted(node["children"].keys())

    def mkdir(self, path: str) -> None:
        # Traverse/create directories
        node = self.root
        parts = path.split("/")[1:]  # Skip leading "/"
        for part in parts:
            if part not in node["children"]:
                node["children"][part] = {"children": {}, "content": ""}
            node = node["children"][part]

    def addContentToFile(self, filePath: str, content: str) -> None:
        # Traverse/create path to file
        node = self.root
        parts = filePath.split("/")[1:]  # Skip leading "/"
        for part in parts:
            if part not in node["children"]:
                node["children"][part] = {"children": {}, "content": ""}
            node = node["children"][part]
        # Append content to file
        node["content"] += content

    def readContentFromFile(self, filePath: str) -> str:
        # Traverse to file, return content
        node = self.root
        parts = filePath.split("/")[1:]  # Skip leading "/"
        for part in parts:
            node = node["children"][part]
        return node["content"]

• Lines 3-4: Initialize root node with empty children and content.
• Lines 7-15: ls:
• Traverse to path.
• Return file name if content exists, else sorted directory contents.
• Lines 17-23: mkdir:
• Split path, create nodes if missing.
• Lines 25-33: addContentToFile:
• Traverse/create path, append content to file node.
• Lines 35-41: readContentFromFile:
• Traverse to file, return content.
• Time Complexity: O(m) per operation—path traversal (m = path length).
• Space Complexity: O(n)—total nodes in trie (n = unique path components).

It’s like a file-system crafting wizard!

Alternative Solution: Flat Dictionary Approach

Why an Alternative Approach?

The flat dictionary approach stores full paths as keys with content or a flag for directories, running in O(n) time for ls (due to scanning all keys) and O(1) for other operations, with O(n) space. It’s simpler but less efficient for directory listing, making it a good baseline for small systems or understanding.

How It Works

Picture this as a flat-file organizer:

• Step 1: Use dictionary with paths as keys.
• Step 2: ls: Scan keys, filter by prefix, return matches.
• Step 3: mkdir: Add path with empty content.
• Step 4: addContentToFile: Add/update path with content.
• Step 5: readContentFromFile: Retrieve content by path.

It’s like a simple path logger!

Step-by-Step Example

Example: Operations

• Init: files = {}.
• mkdir("/a/b"): files["/a/b"] = "".
• addContentToFile("/a/b/c.txt", "hello"): files["/a/b/c.txt"] = "hello".
• ls("/a/b"): Scan keys, return ["c.txt"].
• readContentFromFile("/a/b/c.txt"): Return "hello".

Code for Alternative Approach

class FileSystem:
    def __init__(self):
        self.files = {}

    def ls(self, path: str) -> List[str]:
        if path in self.files and self.files[path]:
            return [path.split("/")[-1]]
        result = []
        for key in self.files:
            if key.startswith(path + "/") and key[len(path) + 1:].count("/") == 0:
                result.append(key[len(path) + 1:])
        return sorted(result)

    def mkdir(self, path: str) -> None:
        self.files[path] = ""

    def addContentToFile(self, filePath: str, content: str) -> None:
        if filePath not in self.files:
            self.files[filePath] = ""
        self.files[filePath] += content

    def readContentFromFile(self, filePath: str) -> str:
        return self.files[filePath]

• Line 4: Initialize flat dictionary.
• Lines 7-14: ls: Scan keys, filter direct children.
• Lines 16-17: mkdir: Add path with empty content.
• Lines 19-22: addContentToFile: Add/update content.
• Line 24-25: readContentFromFile: Return content.
• Time Complexity: O(n) for ls, O(1) others—key scan vs. lookup.
• Space Complexity: O(n)—dictionary storage.

It’s a flat-file manager!

Comparing the Two Solutions

• Trie (Best):
• Pros: O(m) all operations, O(n), hierarchical.
• Cons: More complex structure.
• Flat Dictionary (Alternative):
• Pros: O(n) ls, O(1) others, O(n), simpler.
• Cons: Slower listing.

Trie wins for efficiency and realism!

Additional Examples and Edge Cases

• Root only: Empty list.
• Nested dirs: Correct listing.
• Empty content: Handled as file.

Trie excels in all scenarios!

Complexity Recap

• Trie: Time O(m) per op, Space O(n).
• Flat: Time O(n) ls, O(1) others, Space O(n).

Trie’s the efficiency champ!

Key Takeaways

• Trie: File system finesse—learn at Python Basics!
• Flat: Simple storage.
• Design: Files are fun.
• Python: Trie or flat, your pick!

Final Thoughts: Build That File System!

LeetCode 588: Design In-Memory File System in Python is a creative design challenge. Trie-based directory structure is your fast track, while flat dictionary offers a simpler dive. Want more? Try LeetCode 208: Implement Trie or LeetCode 146: LRU Cache. Ready to design? Head to Solve LeetCode 588 on LeetCode and craft that file system today!