摘要

在日常开发中，处理文件路径的逻辑非常常见，尤其是涉及目录层级结构的时候。比如在 IDE 里显示文件目录树、在服务器端解析配置路径，或者在日志系统里定位文件存放位置，都需要类似的层级计算逻辑。

这道 LeetCode 388 文件的最长绝对路径 就是个非常典型的模拟文件系统的题目：我们需要根据给定的字符串描述的文件系统结构，找出路径最长的那个文件，并返回它的路径长度。

描述

假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：

这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。subdir1 包含文件 file1.ext 和子目录 subsubdir1；subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。

在文本格式中，如下所示(⟶表示制表符)：

dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext

如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"。'\n' 和 '\t' 分别是换行符和制表符。

文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。上面例子中，指向 file2.ext 的 绝对路径 是 "dir/subdir2/subsubdir2/file2.ext"。每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，其中 name 和 extension由字母、数字和/或空格组成。

给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向 文件 的 最长绝对路径 的长度 。 如果系统中没有文件，返回 0。

示例 1：

输入： input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
输出： 20
解释： 只有一个文件，绝对路径为 "dir/subdir2/file.ext" ，路径长度 20

示例 2：

输入： input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
输出： 32
解释： 存在两个文件：
"dir/subdir1/file1.ext" ，路径长度 21
"dir/subdir2/subsubdir2/file2.ext" ，路径长度 32
返回 32 ，因为这是最长的路径

示例 3：

输入： input = "a"
输出： 0
解释： 不存在任何文件

示例 4：

输入： input = "file1.txt\nfile2.txt\nlongfile.txt"
输出： 12
解释： 根目录下有 3 个文件。
因为根目录中任何东西的绝对路径只是名称本身，所以答案是 "longfile.txt" ，路径长度为 12

提示：

• 1 <= input.length <= 104
• input 可能包含小写或大写的英文字母，一个换行符 '\n'，一个制表符 '\t'，一个点 '.'，一个空格 ' '，和数字。

题解答案

直观的解法是：

1. 用 split("\n") 把输入按行拆开；
2. 每一行根据 \t 数量确定它的层级；
3. 用一个栈（或者字典）记录每一层目录累计的路径长度；
4. 如果当前是目录，就把它的长度存起来；
5. 如果当前是文件，就更新答案为 max(当前路径长度, 答案)。

题解代码分析

我们来看一份 Swift 的实现代码，逻辑清晰且符合 O(n) 时间复杂度要求：

import Foundation

class Solution {
    func lengthLongestPath(_ input: String) -> Int {
        // 用字典存储每一层的路径长度
        var pathLen = [Int: Int]()
        pathLen[0] = 0  // 根目录前缀长度为 0
        var maxLen = 0
        
        // 按行拆分目录结构
        let lines = input.split(separator: "\n")
        
        for line in lines {
            // 去掉前缀 \t，剩下就是名字
            let name = line.replacingOccurrences(of: "\t", with: "")
            // 层级就是 \t 的数量
            let depth = line.count - name.count
            
            if name.contains(".") {
                // 是文件
                let length = (pathLen[depth] ?? 0) + name.count
                maxLen = max(maxLen, length)
            } else {
                // 是目录，需要 +1，因为要加 "/"
                pathLen[depth + 1] = (pathLen[depth] ?? 0) + name.count + 1
            }
        }
        
        return maxLen
    }
}

代码拆解

• pathLen[depth] 记录当前层级的前缀路径长度；
• 判断是否是文件：只要名字里有 "."，那就是文件；
• 如果是文件：计算总长度 (父路径长度 + 文件名长度)，更新 maxLen；
• 如果是目录：更新下一层的路径长度，记得加上 / 占 1 个字符；
• 最终返回 maxLen。

这样，整个遍历只要一次，完全符合 O(n)。

示例测试及结果

我们来跑几个示例：

let solution = Solution()

print(solution.lengthLongestPath("dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"))
// 输出：20 -> "dir/subdir2/file.ext"

print(solution.lengthLongestPath("dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"))
// 输出：32 -> "dir/subdir2/subsubdir2/file2.ext"

print(solution.lengthLongestPath("a"))
// 输出：0 -> 没有文件

print(solution.lengthLongestPath("file1.txt\nfile2.txt\nlongfile.txt"))
// 输出：12 -> "longfile.txt"

结果完全符合预期。

时间复杂度

• 遍历每一行字符串，每一行处理时间是 O(1)，所以整体是 O(n)，其中 n 是输入字符串长度。

空间复杂度

• 我们只用一个字典来存储层级的路径长度，最多深度不会超过输入行数，所以空间复杂度是 O(depth)，在题目约束下近似看作 O(n)。

总结

这道题虽然是字符串题，但本质上考的是如何用栈/字典来模拟文件路径。

几个要点：

1. 用 split("\n") 拆行，\t 来确定层级；
2. 区分目录和文件，更新路径长度；
3. 文件的时候更新最大路径长度。

在实际开发里，比如日志里存储嵌套目录的层级信息，或者 IDE 需要解析字符串描述的文件结构，都能用类似的思路。

——所以这题不仅仅是刷题练手，还能帮我们在遇到层级结构解析问题时，多一个思路。