LeetCode 588. 设计内存文件系统
题目描述
题意分析
在内存中维护文件和目录，支持四个接口：
ls查询文件名或目录的直接子项，mkdir补齐目录路径，addContentToFile创建文件或追加内容，readContentFromFile读取完整内容。目录可以逐级嵌套，同一目录下的名字定位一个子项；不同目录中可以出现相同名字。用一棵按路径层级组织的树，就能让这些接口共用同一套定位过程。
解法：Trie 模拟文件系统
核心思路
[!blue]
每个节点保存children、file和内容缓冲区。children将一个完整路径段映射到子节点，file区分文件与目录，内容缓冲只在文件节点中使用。根节点对应/，路径的共同前缀自然共享同一批目录节点。
traverse(path, create)从根开始，按斜杠切分路径，逐段沿children下降。路径开头的空段要跳过，根路径直接返回根节点。create为真时创建缺失节点，因此mkdir一次遍历就能补齐多级目录，已经存在的部分直接复用。文件写入也先定位节点，再设置文件标记并向内容缓冲追加；重复写入不会清空旧内容。读取只沿已有路径定位，返回该节点内容，不创建新的目录或文件。
ls定位后按节点类型处理：文件返回只含自身名字的列表，目录返回children的键，也就是直接子项的名字，不递归列出后代。子节点保存在哈希表中，遍历顺序不确定，因此目录结果必须排序后返回。
解题步骤
- 初始化根目录，所有操作都从根节点开始解析绝对路径。
mkdir使用允许创建的定位过程，每个缺失路径段都创建为目录节点。addContentToFile定位或创建末尾节点，将其标记为文件，用可增长缓冲追加本次内容。readContentFromFile定位已有文件并返回内容；ls定位后返回文件自身名字，或排好序的直接子项名字。空目录的
children为空，列举结果自然为空列表；对/的操作直接作用于根节点，不会创建名字为空的额外层级。
代码实现
class FileSystem {
private static class Node {
// 路径段是完整名字而非单字符，所以用哈希表而不是定长数组。
Map<String, Node> children = new HashMap<>();
// addContentToFile 语义是追加，用可增长缓冲避免反复复制。
StringBuilder content = new StringBuilder();
boolean file;
}
private final Node root = new Node();
public List<String> ls(String path) {
Node node = traverse(path, false);
// 路径指向文件时，只返回文件名本身。
if (node.file) {
int idx = path.lastIndexOf('/');
return Arrays.asList(path.substring(idx + 1));
}
List<String> res = new ArrayList<>(node.children.keySet());
// 哈希表不保证顺序，题目要求字典序。
Collections.sort(res);
return res;
}
public void mkdir(String path) {
// 创建是遍历的副作用：路径上缺失的每一级都会被补齐。
traverse(path, true);
}
public void addContentToFile(String filePath, String content) {
Node node = traverse(filePath, true);
node.file = true;
node.content.append(content);
}
public String readContentFromFile(String filePath) {
return traverse(filePath, false).content.toString();
}
// create 开关集中表达「写路径创建、读路径不创建」的语义差异。
private Node traverse(String path, boolean create) {
Node cur = root;
// 根路径直接返回根节点，无需继续按路径段下降。
if ("/".equals(path)) {
return cur;
}
String[] parts = path.split("/");
// 路径以 / 开头，第 0 段必为空串，从 1 开始。
for (int i = 1; i < parts.length; i++) {
String name = parts[i];
if (!cur.children.containsKey(name)) {
if (!create) {
return null;
}
cur.children.put(name, new Node());
}
cur = cur.children.get(name);
}
return cur;
}
}
import (
"sort"
"strings"
)
type node588 struct {
// 路径段是完整名字而非单字符，所以用哈希表而不是定长数组。
children map[string]*node588
// AddContentToFile 语义是追加，用可增长缓冲避免反复复制。
content strings.Builder
file bool
}
type FileSystem struct {
root *node588
}
func Constructor() FileSystem {
return FileSystem{root: &node588{children: make(map[string]*node588)}}
}
func (fs *FileSystem) Ls(path string) []string {
node := fs.traverse(path, false)
// 路径指向文件时，只返回文件名本身。
if node.file {
parts := strings.Split(path, "/")
return []string{
parts[len(parts)-1],
}
}
res := make([]string, 0, len(node.children))
for name := range node.children {
res = append(res, name)
}
// map 遍历顺序随机，题目要求字典序。
sort.Strings(res)
return res
}
func (fs *FileSystem) Mkdir(path string) {
// 创建是遍历的副作用：路径上缺失的每一级都会被补齐。
fs.traverse(path, true)
}
func (fs *FileSystem) AddContentToFile(filePath string, content string) {
node := fs.traverse(filePath, true)
node.file = true
node.content.WriteString(content)
}
func (fs *FileSystem) ReadContentFromFile(filePath string) string {
return fs.traverse(filePath, false).content.String()
}
// create 开关集中表达「写路径创建、读路径不创建」的语义差异。
func (fs *FileSystem) traverse(path string, create bool) *node588 {
cur := fs.root
// 根路径直接返回根节点，无需继续按路径段下降。
if path == "/" {
return cur
}
parts := strings.Split(path, "/")
// 路径以 / 开头，第 0 段必为空串，从 1 开始。
for i := 1; i < len(parts); i++ {
name := parts[i]
if cur.children[name] == nil {
if !create {
return nil
}
cur.children[name] = &node588{children: make(map[string]*node588)}
}
cur = cur.children[name]
}
return cur
}
复杂度分析
- 时间复杂度：设路径长为 P、本次追加或读取的内容长为 C、目录直接子项数为 d、最大名字长为 H。定位期望 $O(P)$，追加期望摊还 $O(P+C)$，目录列举 $O(P+dH\log(d+1))$；读取 Java 为 $O(P+C)$，Go 当前缓冲转字符串无需复制内容，定位成本为主。
- 空间复杂度：持久存储与节点数、名字总字符量及文件内容总量成正比；临时路径切分和目录结果另占相应空间。
关键点总结
[!green]
- ls 只返回直接子项，文件路径则返回文件自身名字。
- 文件与目录共享节点结构，由标记区分接口行为。
- 读写共用路径定位，创建权限由操作语义决定。
易错点总结
[!yellow]
- 追加写成覆盖：之前内容丢失。
- 文件路径直接列 children：会返回空目录列表而非文件名。
- 路径切分不跳过开头空段：可能创建名字为空的错误节点。
- 目录列表不排序：哈希表遍历不能保证字典序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1166. 设计文件系统 | 中等 | 同样按路径层级维护节点，原题只存路径值，本题还要区分目录和文件并支持内容追加及列表。 |
| 208. 实现 Trie (前缀树) | 中等 | 可把路径组件当作Trie的一层，而非逐字符建边，复用逐级定位节点的结构。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！