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

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 百度
标签
字符串 深度优先搜索 栈

题目描述

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

image-20260928223927589

image-20260928223927591

image-20260928223927592

题意分析

输入用换行分隔目录或文件，用每行开头的制表符数量表示深度。要求从根目录到某个文件的最长绝对路径长度，目录之间的 / 也计入；目录本身不作为答案，没有文件时返回 0。

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

核心思路

[!blue]

输入已经按目录层级展开，一个条目的父目录总会出现在它之前。题目只要长度，不需要建立目录树或反复拼接路径；保存当前各层祖先路径的长度即可。

定义 stack[depth] 为深度 depth 的当前条目之前，完整父路径的长度，包含父目录后面的 /。根层没有父路径，因此 stack[0] = 0。去掉行首 depth 个制表符后，剩余字符串才是当前名称。

若当前是目录，它会成为下一层条目的父目录，因此写入 stack[depth + 1] = stack[depth] + name.length + 1，最后的 1 是连接孩子所需的斜杠。若当前是文件，它的完整路径长度就是 stack[depth] + name.length，末尾不再加斜杠，用这个值更新答案。

题目保证文件系统格式有效，目录名称不含点，而文件名包含扩展名，所以可用名称中是否存在 . 区分文件与目录。回到同层或更浅层时，不必清空整个深层数组：同层条目继续读取共同父路径；一旦进入新分支，父目录又会先覆盖它的下一层槽位，旧分支不会参与新路径。

解题步骤

  1. 按 \n 拆分输入，创建按深度索引的路径长度数组，答案初始化为 0。
  2. 对每一行，仅统计开头连续的 \t 得到深度，再取出完整名称。
  3. 名称含点时，计算文件完整路径长度并更新最大值。
  4. 否则将当前目录路径加上末尾斜杠，写入下一层的父路径长度。
  5. 全部条目处理完后返回答案；没有文件时答案一直为 0。

代码实现

// 数组 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;
    }
}

import "strings"

// 数组 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)$，扫描缩进、名称与文件标记的总字符量线性。
  • 空间复杂度：$O(n)$，分行结果与按深度索引的前缀数组。

关键点总结

[!green]

  • 槽位保存的是当前条目之前的父路径，不含当前名称。
  • 目录追加斜杠，文件末尾不再加斜杠。
  • 按深度覆盖数组就能模拟祖先栈，无需为了退出目录而逐个弹出。

易错点总结

[!yellow]

  • 目录写当前层而非下一层，会污染兄弟前缀。
  • 文件也加一，会多算尾部斜杠。
  • 以第一行长度初始化答案，会在没有文件时返回非零。
  • 名称可以包含空格，不能用去除首尾空白的操作代替只去掉行首制表符。

相似题目

题目 难度 关联与区别
71. 简化路径 中等 同样处理目录层级，本题从缩进读取父子关系并累计长度，原题规范化给定路径中的点目录。
385. 迷你语法分析器 中等 同样解析嵌套结构，本题深度由制表符给出，原题深度由括号给出。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/66430550
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！