题解

文件系统由于是从 path 进行组成一颗文件树，所以就可以一种经典 Tire 解法。

算法笔记-Tire 树

简单来说就是把 path 每个字母拆开，遇到斜杠说明是另外的文件或者文件夹，那么就另起一颗子树。

树的结构很简单：

class Node:
    def __init__(self):
        self.child=defaultdict(Node)
        self.content=""

这种结构带来的重复查询效果是显著的：O(k) k == len(path)

但是由于我们存储了大量的重复字符在 Tire 中，其实十分损耗内存空间，而构建则是 O(n)

在 mkdir 中，可能遇到这种极端情况，就是每次构建的 path 都没有相同前缀，那么这种情况是最耗时的。

Python

from typing import List
from collections import defaultdict
class Node:
    def __init__(self):
        self.child=defaultdict(Node)
        self.content=""

class FileSystem:

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

    def find(self, path: str) -> Node:
        curr = self.root
        if len(path) == 1:
          return curr
        for word in path.split("/")[1:]:
          curr = curr.child[word]
        return curr
        
    def ls(self, path: str) -> List[str]:
        curr = self.find(path)
        if curr.content:
          #  file path, returns a list that only contains this file's name.
          return [path.split("/")[-1]]
        return sorted(curr.child.keys())

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

    def addContentToFile(self, filePath: str, content: str) -> None:
        curr = self.find(filePath)
        curr.content += content

    def readContentFromFile(self, filePath: str) -> str:
        curr = self.find(filePath)
        return curr.content