LeetCode 588 Design In-Memory File System

LeetCode

<div>

Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

• FileSystem() Initializes the object of the system.
• List<String> ls(String path)
  • If path is a file path, returns a list that only contains this file's name.
  • If path is a directory path, returns the list of file and directory names in this directory.The answer should in lexicographic order.
• void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.
• void addContentToFile(String filePath, String content)
  • If filePath does not exist, creates that file containing given content.
  • If filePath already exists, appends the given content to original content.
• String readContentFromFile(String filePath) Returns the content in the file at filePath.

Example 1:

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

Explanation FileSystem fileSystem = new FileSystem(); fileSystem.ls("/"); // return [] fileSystem.mkdir("/a/b/c"); fileSystem.addContentToFile("/a/b/c/d", "hello"); fileSystem.ls("/"); // return ["a"] fileSystem.readContentFromFile("/a/b/c/d"); // return "hello" </pre>

Constraints:

• 1 <= path.length, filePath.length <= 100
• path and filePath are absolute paths which begin with '/' and do not end with '/' except that the path is just "/".
• You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
• 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.
• 1 <= content.length <= 50
• At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.

</div>

题目大意：

设计文件系统

解题思路：

如数据库系统的B+树一样，用Trie

解题步骤：

N/A

注意事项：

1. TrieNode含children和files，都是dict，只能是目录节点。因为不知道最后一个路劲部分是文件还是目录，所以ls里面需要遍历直到倒数第二个节点，再判断是哪种情况。另一个种设计是采取is_file, content，既可以是目录节点也可以是文件节点，本文采取前者
2. ls:题目要求目录可以含目录和文件。两种情况：若是文件，返回[文件]含在一个list中；若是目录，返回它下面的目录+文件
3. ls:返回结果要排序
4. ls:输入path可以是/或/a/b，所以/要特殊化处理，只能是目录，所以只有一种情况：目录和文件
5. _dir而不是dir, path而不是filepath，注意变量要用同一个

Python代码：

class Solution(TestCases):

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

    def ls(self, path: str) -> List[str]:  # req remember /a not /a/
        if path == '/':
            return sorted(list(self.root.children.keys()) + list(self.root.files.keys())) # remember

        dirs = path[1:].split('/')
        it = self._ls(dirs[:-1])
        if dirs[-1] in it.files:
            return [dirs[-1]]
        else: # return files if no dir, no mixed types in same dir
            return sorted(list(it.children[dirs[-1]].children.keys()) + list(it.children[dirs[-1]].files.keys()))

    def mkdir(self, path: str) -> None:
        path = path[1:]
        dirs = path.split('/') # [a,b,c]
        self._mkdir(dirs)

    def addContentToFile(self, filePath: str, content: str) -> None:
        filePath = filePath[1:]
        dirs = filePath.split('/') # [a,b,c]
        it = self._mkdir(dirs[:-1])
        filename = dirs[-1]
        if filename not in it.files:
            it.files[filename] = ''
        it.files[filename] += content

    def readContentFromFile(self, filePath: str) -> str:
        filePath = filePath[1:]
        dirs = filePath.split('/')  # [a,b,c]
        it = self._ls(dirs[:-1])
        return it.files[dirs[-1]]

    def _ls(self, dirs):
        it = self.root
        for _dir in dirs:
            it = it.children[_dir]
        return it

    def _mkdir(self, dirs):
        it = self.root
        for _dir in dirs:
            it = it.children[_dir]
        return it

class TrieNode:

    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.files = collections.defaultdict(str) # use dict coz filename can't be duplicate and faster for lookup

算法分析：

时间复杂度为O(n)，空间复杂度O(n), n为路径长度