LeetCode 588. 设计内存文件系统

2021-03-12 HGNULB 约 14 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 588. 设计内存文件系统

题意分析

设计一个内存文件系统，支持四个接口：ls(path) 列出路径下的内容、mkdir(path) 创建目录（含中间缺失的各级目录）、addContentToFile(filePath, content) 向文件追加内容（文件不存在则创建）、readContentFromFile(filePath) 读取文件全部内容。所有路径都以 / 开头，且题目保证输入合法。

先看数据形态。路径 /a/b/c 天然是一串用 / 分隔的名字，而且不同路径共享前缀——/a/b/c 与 /a/b/d 共用 /a/b 这一段。这正是前缀树（Trie）的定义域：把每一段路径名当作一条边、把目录当作节点，整个文件系统就是一棵以根目录为根的树，路径查找退化成沿着名字逐层下行。与字符 Trie 唯一的区别是边上标的是整个名字而不是单个字符，所以子节点用 Map<String, Node> 而不是长度 26 的数组。

再看接口的语义差异。mkdir 要求「路径中不存在的中间目录也一并创建」，addContentToFile 要求「文件不存在则创建」——这两个都是写路径，走到哪一层缺哪一层就补上。而 ls 和 readContentFromFile 是读路径，题目保证目标存在，不该顺手创建节点。四个接口只在「缺节点时创建还是不创建」这一点上不同，其余的逐层下行逻辑完全一样，所以应当抽出一个带开关的公共遍历函数。

ls 的返回规则是本题最容易读漏的地方：如果路径指向一个文件，返回的是只含该文件名的单元素列表；如果指向目录，返回目录下所有子项（文件与子目录都算）的名字，并按字典序排序。两种情形的返回内容完全不同，必须先判断节点类型再决定怎么返回。

addContentToFile 是追加而不是覆盖，所以文件内容要用可增长的缓冲区（StringBuilder / strings.Builder）而不是简单赋值。

边界：根路径 "/" 要单独处理——按 / 切分后会得到空片段，直接进循环会去找一个名为空串的子节点；一个节点既可能是目录也可能是文件，需要一个标志位区分；ls("/") 在空系统上应返回空列表而不是报错。

解法：Trie 模拟文件系统

核心思路

最容易想到的偷懒做法是用一张 Map<完整路径字符串, 内容> 把所有文件平铺存起来。读写单个文件确实简单，但 ls 会变成灾难：要列出 /a/b 下的子项，必须遍历整张表、对每个键做前缀匹配、再截出下一段名字并去重。单次 ls 是 $O(总文件数 \times 路径长度)$，而且「空目录」根本无法表示（mkdir 创建了目录但没有任何文件，平铺表里留不下痕迹）。

问题的根源在于平铺结构丢掉了层级信息。而层级恰恰是文件系统的本质，也是 ls 唯一关心的东西。所以应当让数据结构本身承载层级：每一级目录是一个节点，节点通过「名字 → 子节点」的映射连向下一级。这样 ls 就退化成「走到目标节点，把它的子映射的键集合取出来」，与系统总规模无关，只与该目录的子项数有关。

节点的定义要同时容纳目录和文件两种角色：children 是「名字 → 子节点」的映射（目录用），content 是可追加的内容缓冲（文件用），file 是一个布尔标志用来区分。之所以不拆成两个类，是因为 ls 拿到节点后需要先判类型再决定行为，同一个字段布局最省事；而且题目保证同名不会既是文件又是目录，一个标志位足够。

四个接口的公共部分抽成 traverse(path, create)：从根出发，把路径按 / 切成若干段，逐段在 children 里查找并下行。create 为真时（mkdir、addContentToFile）遇到缺失的名字就新建节点再继续；为假时（ls、read）遇到缺失直接返回空。这个开关把「写路径会创建、读路径不创建」这条语义差异集中到了一处，其余三个接口都变成两三行。

路径切分有个细节："/a/b".split("/") 得到的是 ["", "a", "b"]——因为路径以 / 开头，第一段是空串。所以循环要从下标 1 开始，跳过这个空片段。而 "/" 切分后只得到 [""]（甚至可能是空数组），循环压根不会执行，但为了语义清晰仍然把它单独判掉、直接返回根节点。

不变量：任意时刻，从根出发沿路径各段下行所到达的节点，就是该路径对应的目录或文件；节点的 children 恰好是该目录下全部直接子项。只要 traverse 是唯一的下行入口，这个不变量就不会被破坏，四个接口也就天然一致。

ls 的排序放在返回前做而不是维护有序结构，是因为 ls 的调用频率通常低于写操作，用 HashMap 保证 $O(1)$ 的写入、只在 ls 时付一次 $O(d \log d)$ 的排序代价，是更划算的取舍。若题目改成 ls 极其频繁，则可以换成 TreeMap 把排序摊进插入。

解题步骤

定义节点类：children 为 Map<String, Node>、content 为可追加缓冲、file 为布尔标志。为什么：路径段是完整单词而非单字符，所以子节点用哈希表而不是定长数组；content 用 StringBuilder 是因为 addContentToFile 语义是追加，反复字符串拼接会产生 $O(L^2)$ 的复制；file 标志让 ls 能区分两套返回规则。

持有一个 root 节点代表根目录 /。为什么：根目录没有名字、也不是任何节点的子项，必须单独持有作为所有遍历的起点。

实现 traverse(path, create)：先判 path 等于 "/" 则直接返回 root。为什么：根路径切分后只剩空片段，进循环会去查找名为空串的子节点；单独判掉既避免了这个坑，也让「根目录」这个特殊情形一眼可见。

把路径按 / 切分，循环从下标 1 开始。为什么：路径以 / 开头，切分结果的第 0 段必然是空串；从 1 开始正好跳过它，剩下的每一段都是一级名字。

每一段先查 children，缺失时：create 为真则新建节点，为假则返回空。为什么：这一个开关同时表达了 mkdir 的「递归创建中间目录」和 ls 的「只读不创建」；把差异收在一处，四个接口的行为就不会各自漂移。

mkdir 直接调用 traverse(path, true) 并丢弃返回值。为什么：创建这个动作本身就是遍历的副作用，路径上每一级缺失的目录都会在下行过程中被补齐，不需要额外逻辑。

addContentToFile 调用 traverse(filePath, true)，把节点标记为文件并 append 内容。为什么：文件不存在时要创建，所以开关为真；标记 file = true 是为了让后续 ls 走文件分支；用 append 而不是赋值，因为语义是追加。

readContentFromFile 调用 traverse(filePath, false) 后返回缓冲的字符串形式。为什么：读操作不应产生副作用，开关为假；题目保证文件存在，所以不必处理空返回。

ls 先定位节点，若 node.file 为真，取路径中最后一个 / 之后的部分作为文件名，返回单元素列表。为什么：题目规定路径指向文件时只返回文件名本身；用「最后一个 / 之后」来截取，不依赖路径深度，任何层级都适用。

否则取 children 的键集合，排序后返回。为什么：目录下的子项既包括子目录也包括文件，它们都在 children 里；题目要求字典序，而哈希表不保证顺序，必须显式排序。

走一遍一串完整的调用。初始只有一个 root。

ls("/")：traverse 命中 "/" 分支直接返回 root；root.file 为假，取 root.children 的键集合——此时为空，排序后返回 []。

mkdir("/a/b/c")：切分得 ["", "a", "b", "c"]，从下标 1 开始。查 root.children["a"] 不存在，create 为真，新建节点并下行；同理创建 b、c。此时树形为 root → a → b → c，三个节点的 file 都是假。

addContentToFile("/a/b/c/d", "hello")：切分得 ["", "a", "b", "c", "d"]。a、b、c 都已存在，直接下行；d 不存在，因 create 为真而被创建。随后把 d 标记为文件，向它的缓冲追加 "hello"。

ls("/")：返回 root.children 的键，只有 ["a"]。注意这里返回的是子目录名，而不是深层的文件名——ls 只看一层。

readContentFromFile("/a/b/c/d")：一路下行到 d，返回 "hello"。

ls("/a/b/c/d")：下行到 d，d.file 为真，走文件分支——取路径中最后一个 / 之后的部分得 "d"，返回 ["d"]。这正是「路径指向文件时只返回文件名」那条规则，若不判 file 而直接返回 children 的键集合，会得到空列表 []，是本题最典型的错误。

addContentToFile("/a/b/c/d", " world")：d 已存在，直接定位并追加，内容变成 "hello world"。若这里写成赋值而非追加，结果会退化成 " world"。

ls("/a/b/c")：c 不是文件，返回它的子项名 ["d"]。

代码实现

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;
    }
}

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
}

复杂度分析

时间复杂度：mkdir、addContentToFile、readContentFromFile 为 $O(p + c)$，ls 为 $O(p + d \log d)$。凭什么：p 是路径字符串长度，切分与逐层哈希查找合计与路径长度成正比，层数不超过 p；c 是本次写入或读取的内容长度，追加是均摊 $O(c)$、读取要把缓冲物化成字符串同样是 $O(c)$；ls 在目录情形下要把 d 个子项名收集起来并排序，排序是 $O(d \log d)$，d 只是该目录的直接子项数，与系统总规模无关——这正是树形结构相对平铺哈希表的核心优势。

空间复杂度：$O(N + C)$。凭什么：N 是所有路径段的总数，每一段对应树上一个节点，共享前缀的路径共用节点，所以不会重复存储；C 是所有文件内容的总长度，存在各自的缓冲里。除此之外只有常数个临时变量与 ls 中长度为 d 的结果列表。

关键点总结

看到「路径」「前缀共享」「按层级列举」三个特征同时出现，就该想到 Trie。文件系统是 Trie 最直观的现实模型，区别只是边上标的是整个名字而非单个字符——因此子节点容器从定长数组换成哈希表。

平铺哈希表和树形结构的分界线在于有没有「列举下一层」的需求。只做单点读写时平铺更简单，一旦要 ls，层级信息就必须显式建模，否则每次都得全表前缀扫描，而且空目录无法表示。

把多个接口的公共下行逻辑抽成带开关的 traverse，是设计题里最值钱的一步。开关（这里是 create）恰好对应了接口之间唯一的语义差异，其余部分零重复，行为也不会各自漂移。面试时先写出这个函数签名，思路的清晰度立刻显现。

一个节点同时承担目录与文件两种角色时，用一个布尔标志区分比拆成两个类型更省事，因为调用方（ls）本来就需要先判类型再分派。

排序放在读取时还是写入时，取决于读写频率的相对大小。用 HashMap + ls 时排序，是「写多读少」的取舍；换成 TreeMap 则把成本摊进每次插入。能主动说出这个权衡，比直接写 Collections.sort 更有说服力。

面试延伸：被问到「怎么支持删除」时，答案是从父节点的 children 里移除对应键，递归释放子树；被问到「怎么支持并发」时，可以按目录粒度加读写锁，或用不可变节点 + 写时复制。

易错点总结

ls 不判 node.file 就直接返回 children 的键集合：ls("/a/b/c/d") 指向文件 → 文件节点没有子项，返回空列表 []，而正确答案是 ["d"]。

ls 返回目录下所有后代而不是直接子项：ls("/") 在存在 /a/b/c/d 时 → 返回 ["a", "b", "c", "d"]，而正确答案只有 ["a"]；ls 只看一层。

ls 忘记排序：Java 的 HashMap、Go 的 map 遍历顺序都不保证 → 同一份数据多次运行返回顺序不同，判题随机失败。

切分路径后从下标 0 开始遍历："/a" 切分得 ["", "a"] → 先去查找名为空串的子节点，create 为真时会凭空创建一个名字为空的目录，ls("/") 里因此多出一个空字符串项。

addContentToFile 用赋值代替追加：先写 "hello" 再写 " world" → 内容变成 " world"，而正确结果是 "hello world"。

addContentToFile 用字符串拼接而非可增长缓冲：向同一文件追加 n 次、每次长度 L → 每次都复制一遍全量内容，总代价 $O(n^2 L)$，大量追加时超时。

addContentToFile 忘记把节点标记为 file：随后 ls 该路径 → 走进目录分支返回空列表，而不是文件名。

readContentFromFile 传入 create = true：读一个不存在的文件时 → 静默创建出一个空文件节点，污染后续 ls 的结果，把一个本该报错的场景变成了难查的脏数据。

mkdir 只创建最后一级、不补齐中间目录：mkdir("/a/b/c") 而 /a 不存在 → 抛空指针或只建出孤立的节点，后续 ls("/") 看不到 a。

用 Map<完整路径, 内容> 平铺存储：mkdir("/a/b") 后 ls("/a") → 空目录在平铺表里没有任何记录，返回空列表而不是 ["b"]；且每次 ls 都要全表前缀扫描，规模一大就慢。

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	Trie 的最小形态，边上是单个字符，子节点可用长度 26 的定长数组
1166. 设计文件系统	中等	只需创建与取值、不支持 `ls`，因此平铺哈希表就够，正好对照本题为何需要树
211. 添加与搜索单词 - 数据结构设计	中等	查询支持通配符 `.`，遇到它要对所有子节点分支递归，查找不再是单路下行
212. 单词搜索 II	困难	把词典建成 Trie 后在网格上回溯，考的是用 Trie 给搜索剪枝
648. 单词替换	中等	沿 Trie 下行找最短匹配前缀即停，考的是提前终止而非走到底
677. 键值映射	中等	节点上挂的是数值并需按前缀求和，涉及更新已存在键时的差值处理
720. 词典中最长的单词	中等	要求路径上每一级都是完整单词，本质是在 Trie 上做受限的深度优先搜索
LCR 062. 实现 Trie (前缀树)	中等	与 208 同题，可直接套用同一套节点定义与插入查找骨架