# 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)