# LeetCode 588: Design In-Memory File System

## Problem Restatement

We need to design an in-memory file system.

The file system must support four operations:

| Operation | Behavior |
|---|---|
| `ls(path)` | If `path` is a file, return only that file name. If `path` is a directory, return its direct children in lexicographic order. |
| `mkdir(path)` | Create the directory path. If middle directories do not exist, create them too. |
| `addContentToFile(filePath, content)` | Create the file if missing, otherwise append `content` to the existing file. |
| `readContentFromFile(filePath)` | Return the full content of the file. |

All paths are absolute paths that begin with `/`. The root directory is `/`. Directory and file names contain lowercase letters. Operations are valid, so we do not need to handle invalid reads or invalid listings. The official statement defines this as a file-system simulation problem with design, trie, hash table, string, and sorting tags.

## Input and Output

The class shape is:

```python
class FileSystem:

    def __init__(self):
        ...

    def ls(self, path: str) -> list[str]:
        ...

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

    def addContentToFile(self, filePath: str, content: str) -> None:
        ...

    def readContentFromFile(self, filePath: str) -> str:
        ...
```

The methods return:

| Method | Return value |
|---|---|
| `FileSystem()` | Initializes an empty file system |
| `ls(path)` | `list[str]` |
| `mkdir(path)` | `None` |
| `addContentToFile(filePath, content)` | `None` |
| `readContentFromFile(filePath)` | `str` |

## Example

Input:

```text
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
```

Output:

```text
[null, [], null, null, ["a"], "hello"]
```

Step by step:

```python
fs = FileSystem()
fs.ls("/")                         # []
fs.mkdir("/a/b/c")                 # creates /a, /a/b, /a/b/c
fs.addContentToFile("/a/b/c/d", "hello")
fs.ls("/")                         # ["a"]
fs.readContentFromFile("/a/b/c/d") # "hello"
```

The file `d` is created under `/a/b/c`.

The root directory now has one child: `a`.

## First Thought: Store Full Paths in Dictionaries

A simple idea is to store directories and files by their full paths.

For example:

```python
directories = {"/", "/a", "/a/b", "/a/b/c"}
files = {
    "/a/b/c/d": "hello"
}
```

This can work, but `ls(path)` becomes awkward.

If we call:

```python
ls("/a")
```

we need to find only direct children of `/a`, not every path that starts with `/a`.

That means we must parse and compare many full path strings.

A real file system is hierarchical, so a hierarchical data structure is cleaner.

## Key Insight

A path is naturally a sequence of components.

For example:

```text
/a/b/c/d
```

has components:

```python
["a", "b", "c", "d"]
```

This suggests a tree.

Each node represents either a directory or a file.

A directory node has children.

A file node stores content.

This is often described as a trie over path components. Each edge is one directory or file name, and each node stores metadata for that path.

## Data Structure

Use a `Node` class.

Each node stores:

| Field | Meaning |
|---|---|
| `children` | Map from child name to child node |
| `is_file` | Whether this node is a file |
| `content` | File content, used only when `is_file` is true |

The root node represents `/`.

```python
class Node:
    def __init__(self):
        self.children = {}
        self.is_file = False
        self.content = []
```

Using a list for `content` lets us append strings efficiently.

When reading, we join the list:

```python
"".join(node.content)
```

## Path Parsing

We need a helper to split paths.

For root:

```python
"/"
```

there are no components.

For a normal path:

```python
"/a/b/c"
```

the components are:

```python
["a", "b", "c"]
```

A helper can be:

```python
def parts(self, path: str) -> list[str]:
    if path == "/":
        return []
    return path.split("/")[1:]
```

We skip the first empty string caused by the leading slash.

## Algorithm for `ls`

If `path` is `/`, return the sorted names of root's children.

Otherwise:

1. Split the path into components.
2. Walk from root to the target node.
3. If the target node is a file, return a list containing only the last component.
4. If the target node is a directory, return sorted child names.

The file case is special.

For example:

```python
ls("/a/b/c/d")
```

should return:

```python
["d"]
```

not the file content and not its children.

## Algorithm for `mkdir`

To create:

```text
/a/b/c
```

we walk through:

```python
["a", "b", "c"]
```

At each component:

1. If the child does not exist, create a new directory node.
2. Move to that child.

This behaves like `mkdir -p`.

## Algorithm for `addContentToFile`

To add content to:

```text
/a/b/c/d
```

we walk through all components.

At each component:

1. If the node does not exist, create it.
2. Move to it.
3. At the last component, mark it as a file.
4. Append content to the file node.

The problem guarantees valid operations, and `addContentToFile` may create the file if it does not exist.

## Algorithm for `readContentFromFile`

1. Split the file path.
2. Walk from root to the target file node.
3. Return `"".join(node.content)`.

## Correctness

The tree contains one node for every directory or file path that has been created. Each edge corresponds to exactly one path component. Therefore, walking from the root through the components of a path reaches exactly the node represented by that path.

For `mkdir`, the algorithm creates every missing component on the path and moves through existing components when they already exist. Thus, after `mkdir(path)`, the directory path exists.

For `addContentToFile`, the algorithm reaches the node for `filePath`, creating missing nodes if needed. It marks the final node as a file and appends the new content. Therefore, repeated calls preserve old content and add new content at the end.

For `readContentFromFile`, the algorithm reaches the file node and joins all appended content pieces in insertion order. This returns exactly the file content.

For `ls`, if the target node is a file, the required result is only the file name. The algorithm returns the final path component. If the target node is a directory, the required result is its direct children in lexicographic order. The algorithm returns the sorted child names. Therefore, every operation matches the required behavior.

## Complexity

Let:

```text
L = number of components in the path
C = number of children in the listed directory
S = total content length of the file being read
```

| Operation | Time | Space |
|---|---:|---:|
| `ls(path)` for file | `O(L)` | `O(1)` apart from output |
| `ls(path)` for directory | `O(L + C log C)` | `O(C)` for output |
| `mkdir(path)` | `O(L)` | `O(L)` for newly created nodes |
| `addContentToFile(filePath, content)` | `O(L + len(content))` | `O(len(content))` |
| `readContentFromFile(filePath)` | `O(L + S)` | `O(S)` for returned string |

The sort in `ls` is needed because directory contents must be returned in lexicographic order.

## Implementation

```python
class Node:
    def __init__(self):
        self.children = {}
        self.is_file = False
        self.content = []

class FileSystem:

    def __init__(self):
        self.root = Node()

    def _parts(self, path: str) -> list[str]:
        if path == "/":
            return []
        return path.split("/")[1:]

    def _walk(self, path: str, create: bool = False) -> Node:
        node = self.root

        for name in self._parts(path):
            if create and name not in node.children:
                node.children[name] = Node()
            node = node.children[name]

        return node

    def ls(self, path: str) -> list[str]:
        node = self._walk(path)

        if node.is_file:
            return [self._parts(path)[-1]]

        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        self._walk(path, create=True)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self._walk(filePath, create=True)
        node.is_file = True
        node.content.append(content)

    def readContentFromFile(self, filePath: str) -> str:
        node = self._walk(filePath)
        return "".join(node.content)
```

## Code Explanation

The `Node` class is the core structure:

```python
class Node:
    def __init__(self):
        self.children = {}
        self.is_file = False
        self.content = []
```

A directory is a node with `is_file = False`.

A file is a node with `is_file = True`.

The constructor creates the root directory:

```python
def __init__(self):
    self.root = Node()
```

The helper `_parts` converts a path into names:

```python
def _parts(self, path: str) -> list[str]:
    if path == "/":
        return []
    return path.split("/")[1:]
```

The helper `_walk` moves through the tree:

```python
def _walk(self, path: str, create: bool = False) -> Node:
    node = self.root

    for name in self._parts(path):
        if create and name not in node.children:
            node.children[name] = Node()
        node = node.children[name]

    return node
```

When `create` is true, missing nodes are created.

When `create` is false, the method assumes the path already exists, which is valid for the given operations.

The `ls` method handles files and directories differently:

```python
def ls(self, path: str) -> list[str]:
    node = self._walk(path)

    if node.is_file:
        return [self._parts(path)[-1]]

    return sorted(node.children.keys())
```

The `mkdir` method only needs to walk with creation enabled:

```python
def mkdir(self, path: str) -> None:
    self._walk(path, create=True)
```

The `addContentToFile` method creates the path if needed, marks the final node as a file, and appends content:

```python
def addContentToFile(self, filePath: str, content: str) -> None:
    node = self._walk(filePath, create=True)
    node.is_file = True
    node.content.append(content)
```

The `readContentFromFile` method joins all appended chunks:

```python
def readContentFromFile(self, filePath: str) -> str:
    node = self._walk(filePath)
    return "".join(node.content)
```

## Testing

```python
def run_tests():
    fs = FileSystem()

    assert fs.ls("/") == []

    fs.mkdir("/a/b/c")
    fs.addContentToFile("/a/b/c/d", "hello")

    assert fs.ls("/") == ["a"]
    assert fs.ls("/a/b/c") == ["d"]
    assert fs.ls("/a/b/c/d") == ["d"]
    assert fs.readContentFromFile("/a/b/c/d") == "hello"

    fs.addContentToFile("/a/b/c/d", " world")
    assert fs.readContentFromFile("/a/b/c/d") == "hello world"

    fs.mkdir("/a/b/e")
    fs.addContentToFile("/a/b/file", "x")
    assert fs.ls("/a/b") == ["c", "e", "file"]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `ls("/")` on empty root | Root initially has no children |
| `mkdir("/a/b/c")` | Creates intermediate directories |
| `addContentToFile` on missing file | Creates a new file |
| `ls` on directory | Returns direct children only |
| `ls` on file | Returns only the file name |
| Append twice | Preserves existing content |
| Multiple children | Confirms lexicographic order |