# 588 Design In-Memory File System

## 588. [Design In-Memory File System](https://leetcode.com/problems/design-in-memory-file-system/)

## 1. Question

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.

**Example:**

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

**Note:**

1. 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`"/"`.
2. 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.
3. 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.

## 2. Implementation

**(1) Trie**

思路: 类似于建一个trie数，每个node代表file system的node，type 1代表是文件， type 0代表是目录。无论是call哪个command，我们都从trieNode的root根据输入的path遍历到相应的trieNode(traverse()函数的作用)，然后再根据具体的command做出对应的操作

```java
class FileSystem {
    class iNode {
        int type;
        String name, content;
        TreeMap<String, iNode> children;

        public iNode(int type, String name) {
            this.type = type;
            this.name = name;
            content = "";
            children = new TreeMap();
        }
    }

    iNode root;

    public FileSystem() {
        root = new iNode(0, "");
    }

    public iNode traverse(String path, boolean isFile) {
        if (path.equals("/")) {
            return root;
        }

        iNode curNode = root;

        String[] names = path.split("/");

        for (int i = 1; i < names.length; i++) {
            String name = names[i];

            if (!curNode.children.containsKey(name)) {
                curNode.children.put(name, new iNode(i == names.length - 1 && isFile ? 1 : 0, name));
            }
            curNode = curNode.children.get(name);
        }
        return curNode;
    }

    public List<String> ls(String path) {
        List<String> res = new ArrayList();
        iNode curNode = traverse(path, false);

        if (curNode.type == 1) {
            res.add(curNode.name);
        }
        else {
            for (String name : curNode.children.keySet()) {
                res.add(name);
            }
        }
        return res;
    }

    public void mkdir(String path) {
        traverse(path, false);
    }

    public void addContentToFile(String filePath, String content) {
        iNode curNode = traverse(filePath, true);
        curNode.content += content;
    }

    public String readContentFromFile(String filePath) {
        iNode curNode = traverse(filePath, true);
        return curNode.content;
    }
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * List<String> param_1 = obj.ls(path);
 * obj.mkdir(path);
 * obj.addContentToFile(filePath,content);
 * String param_4 = obj.readContentFromFile(filePath);
 */
```

## 3. Time & Space Complexity

时间复杂度:O(n), n是输入路径的文件个数，ls, mkdir, addContentToFile和readContentFromFile都一样，空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/trie/588-design-in-memory-file-system.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.