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

Categories:

题目描述
思路分析
1. 解法一：栈记录各层路径长度（推荐）
相似题目

题目描述

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

思路分析

解法一：栈记录各层路径长度（推荐）

核心思路：

按行切分输入，每行前导 ` ` 个数表示层级深度。

用数组 stack[depth] 记录到该层目录的累计长度（含末尾 /）。

若当前为文件，长度为 stack[depth] + len(name)；若为目录，更新下一层长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串总长度。

空间复杂度：O(d)，其中 d 表示最大目录深度。

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"

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
}

相似题目

题目	难度	考察点
71. 简化路径	中等	栈 + 字符串解析
394. 字符串解码	中等	栈
636. 函数的独占时间	中等	栈 + 日志解析
811. 子域名访问计数	中等	字符串统计
1169. 查询无效交易	中等	字符串解析

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/66430550