588. 设计内存文件系统 🔒

题目描述

设计一个内存文件系统，模拟以下功能：

实现文件系统类:

FileSystem() 初始化系统对象
List<String> ls(String path)
- 如果 path 是一个文件路径，则返回一个仅包含该文件名称的列表。
- 如果 path 是一个目录路径，则返回该目录中文件和 目录名 的列表。

答案应该按字典顺序 排列。

void mkdir(String path) 根据给定的路径创建一个新目录。给定的目录路径不存在。如果路径中的中间目录不存在，您也应该创建它们。
void addContentToFile(String filePath, String content)
- 如果 filePath 不存在，则创建包含给定内容 content的文件。
- 如果 filePath 已经存在，将给定的内容 content附加到原始内容。
String readContentFromFile(String filePath) 返回 filePath下的文件内容。

示例 1:

输入: 
["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]
[[],["/"],["/a/b/c"],["/a/b/c/d","hello"],["/"],["/a/b/c/d"]]
输出:
[null,[],null,null,["a"],"hello"]

解释:
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // 返回 []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // 返回 ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // 返回 "hello"

注意:

1 <= path.length, filePath.length <= 100
path 和 filePath 都是绝对路径，除非是根目录 ‘/’ 自身，其他路径都是以 ‘/’ 开头且不以 ‘/’ 结束。
你可以假定所有操作的参数都是有效的，即用户不会获取不存在文件的内容，或者获取不存在文件夹和文件的列表。
你可以假定所有文件夹名字和文件名字都只包含小写字母，且同一文件夹下不会有相同名字的文件夹或文件。
1 <= content.length <= 50
ls, mkdir, addContentToFile, and readContentFromFile 最多被调用 300 次

解法

方法一：前缀树

哈希表实现前缀树。

Python3JavaGo

class Trie:
    def __init__(self):
        self.name = None
        self.isFile = False
        self.content = []
        self.children = {}

    def insert(self, path, isFile):
        node = self
        ps = path.split('/')
        for p in ps[1:]:
            if p not in node.children:
                node.children[p] = Trie()
            node = node.children[p]
        node.isFile = isFile
        if isFile:
            node.name = ps[-1]
        return node

    def search(self, path):
        node = self
        if path == '/':
            return node
        ps = path.split('/')
        for p in ps[1:]:
            if p not in node.children:
                return None
            node = node.children[p]
        return node


class FileSystem:
    def __init__(self):
        self.root = Trie()

    def ls(self, path: str) -> List[str]:
        node = self.root.search(path)
        if node is None:
            return []
        if node.isFile:
            return [node.name]
        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        self.root.insert(path, False)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.root.insert(filePath, True)
        node.content.append(content)

    def readContentFromFile(self, filePath: str) -> str:
        node = self.root.search(filePath)
        return ''.join(node.content)


# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.ls(path)
# obj.mkdir(path)
# obj.addContentToFile(filePath,content)
# param_4 = obj.readContentFromFile(filePath)

class Trie {
    String name;
    boolean isFile;
    StringBuilder content = new StringBuilder();
    Map<String, Trie> children = new HashMap<>();

    Trie insert(String path, boolean isFile) {
        Trie node = this;
        String[] ps = path.split("/");
        for (int i = 1; i < ps.length; ++i) {
            String p = ps[i];
            if (!node.children.containsKey(p)) {
                node.children.put(p, new Trie());
            }
            node = node.children.get(p);
        }
        node.isFile = isFile;
        if (isFile) {
            node.name = ps[ps.length - 1];
        }
        return node;
    }

    Trie search(String path) {
        Trie node = this;
        String[] ps = path.split("/");
        for (int i = 1; i < ps.length; ++i) {
            String p = ps[i];
            if (!node.children.containsKey(p)) {
                return null;
            }
            node = node.children.get(p);
        }
        return node;
    }
}

class FileSystem {
    private Trie root = new Trie();

    public FileSystem() {
    }

    public List<String> ls(String path) {
        List<String> ans = new ArrayList<>();
        Trie node = root.search(path);
        if (node == null) {
            return ans;
        }
        if (node.isFile) {
            ans.add(node.name);
            return ans;
        }
        for (String v : node.children.keySet()) {
            ans.add(v);
        }
        Collections.sort(ans);
        return ans;
    }

    public void mkdir(String path) {
        root.insert(path, false);
    }

    public void addContentToFile(String filePath, String content) {
        Trie node = root.insert(filePath, true);
        node.content.append(content);
    }

    public String readContentFromFile(String filePath) {
        Trie node = root.search(filePath);
        return node.content.toString();
    }
}

/**
 * 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);
 */

type Trie struct {
    name     string
    isFile   bool
    content  strings.Builder
    children map[string]*Trie
}

func newTrie() *Trie {
    m := map[string]*Trie{}
    return &Trie{children: m}
}

func (this *Trie) insert(path string, isFile bool) *Trie {
    node := this
    ps := strings.Split(path, "/")
    for _, p := range ps[1:] {
        if _, ok := node.children[p]; !ok {
            node.children[p] = newTrie()
        }
        node, _ = node.children[p]
    }
    node.isFile = isFile
    if isFile {
        node.name = ps[len(ps)-1]
    }
    return node
}

func (this *Trie) search(path string) *Trie {
    if path == "/" {
        return this
    }
    node := this
    ps := strings.Split(path, "/")
    for _, p := range ps[1:] {
        if _, ok := node.children[p]; !ok {
            return nil
        }
        node, _ = node.children[p]
    }
    return node
}

type FileSystem struct {
    root *Trie
}

func Constructor() FileSystem {
    root := newTrie()
    return FileSystem{root}
}

func (this *FileSystem) Ls(path string) []string {
    var ans []string
    node := this.root.search(path)
    if node == nil {
        return ans
    }
    if node.isFile {
        ans = append(ans, node.name)
        return ans
    }
    for v := range node.children {
        ans = append(ans, v)
    }
    sort.Strings(ans)
    return ans
}

func (this *FileSystem) Mkdir(path string) {
    this.root.insert(path, false)
}

func (this *FileSystem) AddContentToFile(filePath string, content string) {
    node := this.root.insert(filePath, true)
    node.content.WriteString(content)
}

func (this *FileSystem) ReadContentFromFile(filePath string) string {
    node := this.root.search(filePath)
    return node.content.String()
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Ls(path);
 * obj.Mkdir(path);
 * obj.AddContentToFile(filePath,content);
 * param_4 := obj.ReadContentFromFile(filePath);
 */

588. 设计内存文件系统 🔒

题目描述

解法

方法一：前缀树

评论