LeetCode 388. 文件的最长绝对路径

2024-09-10 HGNULB 约 9 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 388. 文件的最长绝对路径

题意分析

输入是一个用换行符和制表符编码的目录树：每一行是一个目录名或文件名，行首制表符的个数表示它在树中的深度，深度为 $d$ 的条目属于它上面最近那个深度为 $d-1$ 的目录。要求找出所有文件的绝对路径中最长的那条的长度；如果整棵树里一个文件都没有，返回 $0$。

绝对路径的长度按「各级名称长度之和，加上层与层之间的斜杠个数」计算，斜杠本身不出现在输入里，需要自己补上。深度为 $d$ 的文件，其路径里恰好有 $d$ 个斜杠。

有两个信号值得留意。第一，题目只要长度，不要路径字符串本身，这意味着完全不必拼接字符串，维护整数长度即可。第二，输入的行序天然就是目录树的先序遍历——处理到某一行时，它的所有祖先都已经在前面出现过。这条性质是把「树上求最长路径」降级成「一趟线性扫描」的关键。

边界方面：区分目录与文件的判据是名称里是否含有 .；根层条目的深度为 $0$，其路径前面不加斜杠；同一层可能有多个兄弟，后面的兄弟必须覆盖掉前一个兄弟留下的信息；文件名本身可能含有多个点，目录名则约定不含点。

解法：栈记录各层路径长度

核心思路

一种直白的做法是先按缩进把输入还原成一棵树，再对树做深度优先搜索求最长文件路径。这样是对的，但要额外建节点、连父子、再遍历一遍，代码量和出错面都不小。

瓶颈其实是「建树」这一步纯属多余。既然行序就是先序遍历，那么当扫到深度为 $d$ 的一行时，它的父目录必然是此前最后一个出现的深度为 $d-1$ 的目录，而这个信息可以在扫描过程中顺手记住。

于是把状态定义为一个按深度索引的数组：$stack[d]$ 表示「当前正在处理的这条分支上，深度为 $d$ 的位置之前的路径前缀长度，含该前缀末尾的斜杠」。换句话说，一个深度为 $d$ 的条目，它的完整路径长度就是 $stack[d] + \text{名称长度}$。根据这个定义，$stack[0] = 0$，因为根层条目前面什么都没有。

维持这个定义的不变量是：每当扫到一个深度为 $d$ 的目录，就立刻写入 $stack[d+1] = stack[d] + \text{名称长度} + 1$，那个 $+1$ 就是这个目录名之后的斜杠。由于行序是先序遍历，处理深度为 $d+1$ 的条目之前，最后一次写入 $stack[d+1]$ 的必定正是它真正的父目录，旧的兄弟分支留下的值被自然覆盖。这就是为什么用数组下标直接覆盖，而不需要真的弹栈。

遇到文件时不写 $stack$，而是用 $stack[d] + \text{名称长度}$ 算出候选答案并更新最大值——文件是路径的终点，后面不会再接斜杠。

解题步骤

按换行符把输入切成若干行。行数不会超过输入长度，据此为长度数组开一个 lines.length + 1 的容量，$+1$ 是因为最深的目录还要写入下一层的槽位。

对每一行，从行首开始数连续的制表符个数得到深度 $d$，剩下的部分就是名称。之所以能这样切分，是因为制表符只作为缩进出现，名称内部不会含有制表符。

判断名称中是否含有 .，据此区分文件与目录。这是题目给定的唯一判据，不能靠有没有扩展名之类的额外猜测。

若是文件，计算 $stack[d] + \text{名称长度}$ 并与当前答案取较大者。这里不加 $1$，因为文件名之后不再有斜杠。

若是目录，写入 $stack[d+1] = stack[d] + \text{名称长度} + 1$。写的是下一层而不是当前层，因为这个值是给它的子条目用的前缀；$+1$ 计入分隔用的斜杠。

不需要任何显式的出栈操作。当扫描从深层回到浅层时，浅层的 $stack$ 值仍然有效（它由更早的祖先写入且从未被更深的条目改动），而深层的陈旧值会被新分支的目录在使用前重新写入。

全部扫完后返回记录的最大值。初值取 $0$ 恰好覆盖了「没有任何文件」的情形。

以 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 走一遍：切分后共七行，长度数组初始全为 $0$，答案 best 为 $0$。第一行 dir，深度 $0$，名称长 $3$ 且不含点，写入 $stack[1] = 0 + 3 + 1 = 4$。第二行 subdir1，深度 $1$，名称长 $7$ 不含点，写入 $stack[2] = 4 + 7 + 1 = 12$。第三行 file1.ext，深度 $2$，名称长 $9$ 含点，候选长度为 $12 + 9 = 21$，best 更新为 $21$，对应路径 dir/subdir1/file1.ext 确实是 $21$ 个字符。第四行 subsubdir1，深度 $2$，名称长 $10$ 不含点，写入 $stack[3] = 12 + 10 + 1 = 23$。第五行 subdir2，深度 $1$，名称长 $7$ 不含点，写入 $stack[2] = stack[1] + 7 + 1 = 4 + 8 = 12$，这一步把上一个兄弟分支留下的同值覆盖掉，之后 $stack[3]$ 的旧值 $23$ 虽然还在数组里，但下一次被读取前必定会被重写。第六行 subsubdir2，深度 $2$，名称长 $10$ 不含点，写入 $stack[3] = 12 + 10 + 1 = 23$，正是这次重写让陈旧值失效。第七行 file2.ext，深度 $3$，名称长 $9$ 含点，候选长度为 $23 + 9 = 32$，大于 $21$，best 更新为 $32$。扫描结束返回 $32$，对应路径 dir/subdir2/subsubdir2/file2.ext，逐字符数确实是 $32$。

代码实现

// 用数组 stack[depth] 记录到该层目录的累计长度（含末尾 /）。
class Solution {
    public int lengthLongestPath(String input) {
        String[] lines = input.split("\n");
        int[] stack = new int[lines.length + 1];
        int best = 0;

        for (String line : lines) {
            int depth = 0;
            while (depth < line.length() && line.charAt(depth) == '\t') {
                depth++;
            }

            String name = line.substring(depth);

            if (name.indexOf('.') >= 0) {
                int length = stack[depth] + name.length();
                if (length > best) {
                    best = length;
                }
            } else {
                stack[depth + 1] = stack[depth] + name.length() + 1;
            }
        }

        return best;
    }
}

// 用数组 stack[depth] 记录到该层目录的累计长度（含末尾 /）。
func lengthLongestPath(input string) int {
    lines := strings.Split(input, "\n")
    stack := make([]int, len(lines)+1)
    best := 0

    for _, line := range lines {
        depth := 0
        for depth < len(line) && line[depth] == '\t' {
            depth++
        }

        name := line[depth:]
        if strings.ContainsRune(name, '.') {
            length := stack[depth] + len(name)
            if length > best {
                best = length
            }
        } else {
            stack[depth+1] = stack[depth] + len(name) + 1
        }
    }

    return best
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为输入字符串的总长度。切分成行遍历了一遍输入；对每行数前导制表符和取子串的代价与该行长度成正比，所有行长度之和仍是 $n$；判断是否含点也是逐字符扫一遍该行。合计常数遍线性扫描。

空间复杂度：$O(n)$。切分产生的行数组总字符量为 $O(n)$，按深度索引的长度数组大小为行数加一，最坏情况下（每行只有一个字符）行数与 $n$ 同阶。

关键点总结

输入自带的先序遍历性质，往往能让「先建树再遍历」直接压缩成一趟扫描。看到缩进表示层级的格式，第一反应应该是找这条性质而不是动手建节点。

只要答案是标量（这里是长度），就不要拼接中间字符串。维护整数累计量既省内存又避免了大量子串复制。

用「按深度索引的数组 + 直接覆盖」代替真正的压栈弹栈，成立的前提是「陈旧值在被读取前必定被重写」。能把这个前提说清楚，才敢省掉出栈逻辑。

状态定义要精确到「含不含末尾分隔符」这种细节。本题把斜杠算进 $stack[d+1]$ 而不是在使用时再补，是让文件分支只写 $stack[d] + len$ 这一行的直接原因。

面试视角：面试官会关注你如何处理「从深层回到浅层」。主动解释为什么不需要弹栈，比默默写完更能体现对不变量的掌控。

面试视角：常见追问是「如果目录名允许含点怎么办」。此时判据要改成由输入格式另行给出（例如按是否有子行判断），能顺口指出这一点说明你意识到了判据的脆弱性。

易错点总结

错误写法：目录分支写成 $stack[d] = stack[d] + len + 1$ 而不是写入 $d+1$ → 层级整体错位一格，对样例中的 dir 会把 $stack[0]$ 改成 $4$，之后所有同层兄弟的前缀被污染，结果偏大。

错误写法：文件分支也加上 $1$，即 $stack[d] + len + 1$ → 每条路径都多算一个不存在的末尾斜杠，样例会返回 $33$ 而非 $32$。

错误写法：把制表符 \t 当成四个空格或按字符数除以四来算深度 → 输入里缩进就是单个制表符，除以四会让所有深度归零，所有文件都被当成根层条目，样例返回 $9$。

错误写法：用 name.endsWith(".ext") 之类的后缀判断代替「是否含点」 → 文件扩展名不固定，含其他扩展名的文件会被当成目录，其路径长度从不参与比较，答案偏小甚至为 $0$。

错误写法：数点时用 line.indexOf('.') 而非在去掉缩进后的名称里找 → 本题制表符里没有点所以恰好不出错，但一旦路径前缀被误拼进 line，判据就会失效；养成先切出名称再判断的习惯更稳。

错误写法：为长度数组只开 lines.length 的容量 → 当最后一行是最深处的目录时，写入 $stack[d+1]$ 会越界；容量必须是行数加一。

错误写法：认为浅层回退时必须显式清空更深层的 $stack$ 值 → 清空本身无害，但若清空后忘记在新分支重写，深层文件会用 $0$ 当前缀，样例中 file2.ext 会算成 $9$。

错误写法：把答案初始化为某个负数或第一行的长度 → 输入中一个文件都没有时（例如只有 "dir"），应当返回 $0$，用负数初值会返回负值，用首行长度会返回 $3$。

错误写法：先把输入整体按 \t 也切一遍，试图一次性拿到深度和名称 → 连续制表符会切出空串，空串的个数与深度的对应关系依赖切分实现的细节，极易差一；逐字符数制表符更可靠。

错误写法：为求最长路径而真的拼接出每条绝对路径再取长度 → 深度大时字符串复制的总代价升到 $O(n^2)$ 量级，且完全没有必要，题目只要长度。

相似题目

题目	难度	考察点
71. 简化路径	中等	路径规范化，栈里存的是目录名且需要真正处理 `.` 与 `..` 出栈
1233. 删除子文件夹	中等	排序后用前缀关系判断包含，考察的是路径之间的比较而非解析
636. 函数的独占时间	中等	同样靠嵌套层级驱动，但需要真正的压栈弹栈来结算区间时长
394. 字符串解码	中等	嵌套结构的展开，栈中要同时保存计数与已构造的片段
385. 迷你语法分析器	中等	由字符串还原嵌套对象，考察分隔符与括号配对的解析细节