LeetCode 588 Design In-Memory File System

LeetCode

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:

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”

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.

题目大意：

设计文件系统

解题思路：

如数据库系统的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为路径长度