LeetCode 第388题：文件的最长绝对路径

📖 文章摘要

本文详细解析LeetCode第388题“文件的最长绝对路径”，这是一道字符串处理题。文章提供了基于栈的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升字符串处理能力的读者。

核心知识点： 字符串、栈、深度优先搜索 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升字符串处理能力的程序员

题目描述

假设我们以下述方式存储文件：

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

文件系统由文件和目录组成，每个文件和目录都有一个唯一的名称。文件系统以字符串形式表示，其中：

每个文件或目录的名称由字母、数字和/或空格组成
每个文件或目录的名称长度不超过20个字符
每个文件或目录的名称不包含特殊字符
每个文件或目录的名称不包含点号(.)，除非它是文件扩展名的一部分

给定一个表示文件系统的字符串，返回文件系统中最长绝对路径的长度。如果文件系统为空，返回0。

示例

示例 1：

输入：input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
输出：20
解释：目录结构如下所示：
dir
    subdir1
    subdir2
        file.ext
最长绝对路径为 "dir/subdir2/file.ext"，其长度为 20

文件路径结构1

示例 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
        subsubdir1
    subdir2
        subsubdir2
            file2.ext
最长绝对路径为 "dir/subdir2/subsubdir2/file2.ext"，其长度为 32

文件路径结构2

示例 3：

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

文件路径结构3

提示

1 <= input.length <= 10^4
input 可能包含小写或大写字母、数字、空格、制表符、换行符和点号
input 是有效的文件系统字符串

解题思路

本题可以使用栈来解决：

将输入字符串按换行符分割
使用栈记录当前路径的长度
根据制表符数量确定当前文件/目录的层级
更新栈，计算当前路径长度
如果是文件，更新最长路径长度

时间复杂度： O(n) 空间复杂度： O(n)

图解思路

文件系统结构

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

处理流程

步骤	操作	说明
1	分割字符串	按换行符分割
2	计算层级	根据制表符数量
3	更新栈	维护当前路径
4	计算长度	更新最长路径

代码实现

C# 实现

public class Solution {
    public int LengthLongestPath(string input) {
        string[] paths = input.Split('\n');
        int[] stack = new int[paths.Length + 1];
        int maxLen = 0;
        
        foreach (string path in paths) {
            int level = path.LastIndexOf('\t') + 1;
            int curLen = stack[level] + path.Length - level + 1;
            stack[level + 1] = curLen;
            
            if (path.Contains(".")) {
                maxLen = Math.Max(maxLen, curLen - 1);
            }
        }
        
        return maxLen;
    }
}

Python 实现

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        paths = input.split('\n')
        stack = [0] * (len(paths) + 1)
        max_len = 0
        
        for path in paths:
            level = path.count('\t')
            cur_len = stack[level] + len(path) - level + 1
            stack[level + 1] = cur_len
            
            if '.' in path:
                max_len = max(max_len, cur_len - 1)
                
        return max_len

C++ 实现

class Solution {
public:
    int lengthLongestPath(string input) {
        vector<int> stack(input.length() + 1, 0);
        int maxLen = 0;
        stringstream ss(input);
        string line;
        
        while (getline(ss, line)) {
            int level = 0;
            while (level < line.length() && line[level] == '\t') {
                level++;
            }
            
            int curLen = stack[level] + line.length() - level + 1;
            stack[level + 1] = curLen;
            
            if (line.find('.') != string::npos) {
                maxLen = max(maxLen, curLen - 1);
            }
        }
        
        return maxLen;
    }
};

执行结果

C# 实现

执行用时：92 ms
内存消耗：24.8 MB

Python 实现

执行用时：28 ms
内存消耗：13.2 MB

C++ 实现

执行用时：4 ms
内存消耗：8.4 MB

性能对比

语言	执行用时	内存消耗	特点
C++	4 ms	8.4 MB	执行效率最高，内存占用最小
Python	28 ms	13.2 MB	代码简洁，内存占用适中
C#	92 ms	24.8 MB	类型安全，内存占用较大

代码亮点

🎯 使用栈优化空间复杂度
💡 高效处理制表符
🔍 处理边界情况
🎨 代码结构清晰，易于维护

常见错误分析

🚫 未正确处理制表符
🚫 路径长度计算错误
🚫 边界条件处理错误
🚫 空间复杂度优化不足

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
栈	O(n)	O(n)	高效，直观	需要额外空间
递归	O(n)	O(n)	结构清晰	栈空间开销大

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第388题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

图解思路

文件系统结构

处理流程

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流