教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读本文将深入讲解 LeetCode 第 388 题「文件的最长绝对路径」这是一道被同时归类为「模拟」与「哈希表」的中等难度字符串处理题。题目把一棵文件系统树以\n与\t编码进单个字符串要求还原目录层级、拼接绝对路径并求最长文件路径长度。读完本文你将掌握用制表符计数定位层级、用哈希表/数组记录每层最新前缀路径这一可复用的字符串解析套路并理解从记录完整路径到只记录路径长度的两级优化思路。该题解完整收录于本仓库 LeetCode/381-390/388. 文件的最长绝对路径中等.md并在 模拟专题索引 与 哈希表专题索引 中均有收录推荐指数 。题目背景与核心考点假设有一个同时存储文件和目录的文件系统dir是根目录中的唯一目录它包含两个子目录subdir1和subdir2subdir1又包含文件file1.ext和子目录subsubdir1subdir2包含子目录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是制表符层级缩进。题目要求给定一个以上述格式表示文件系统的字符串input返回文件系统中指向文件的最长绝对路径的长度如果系统中没有文件返回0。关键约束1 input.length 10^4input可能包含小写或大写的英文字母、换行符\n、制表符\t、点.、空格 和数字每个目录名由字母、数字和/或空格组成每个文件名遵循name.extension格式绝对路径中所有路径段用/连接例如指向file2.ext的绝对路径是dir/subdir2/subsubdir2/file2.ext示例逐例分析示例 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不存在任何文件返回 0。注意这里a是一个目录名不含.不能算作文件。示例 4输入input file1.txt\nfile2.txt\nlongfile.txt 输出12根目录下有 3 个文件。因为根目录中任何东西的绝对路径只是名称本身所以答案是longfile.txt路径长度为 12。这个例子揭示了一个要点位于层级 0根目录的文件其路径就是文件名自身不需要任何前缀。核心思路从缩进还原层级题目输入的本质是把一棵树前序序列化成了带缩进的文本。要还原出每条绝对路径需要解决两个子问题切分以\n为界把字符串切成一个个条目每个条目是一个目录或文件名。定层数出条目开头的\t数量得到其所在层级level。条目去掉\t之后的部分cur就是该层级的名字。归属层级为level的条目一定归属于最新一个层级为level - 1的条目即其直接父目录。由于输入顺序是树的前序遍历父目录一定先于其所有子孙出现所以在遍历过程中维护每个层级最新目录的路径前缀就能在遇到文件时立即拼出完整绝对路径。这正是模拟 哈希表解法的核心遍历输入串的过程就是在内存中重建这棵树的过程。解法一模拟 哈希表记录完整路径为了方便将input记为s。对于每一个文件或文件夹通过扫描到结尾\n的方式取得其名称cur根据cur前面有多少个\t得知其所在层级level。当前条目自然归属到最新一个层级为level - 1的文件夹中因此用哈希表记录每个层级最新的文件夹路径通过字符串拼接得到cur所在的完整路径path并在处理整个s的过程中统计长度最大的文件路径。class Solution { public int lengthLongestPath(String s) { MapInteger, String map new HashMap(); int n s.length(); String ans null; for (int i 0; i n; ) { int level 0; while (i n s.charAt(i) \t level 0) i; int j i; boolean isDir true; while (j n s.charAt(j) ! \n) { if (s.charAt(j) .) isDir false; } String cur s.substring(i, j); String prev map.getOrDefault(level - 1, null); String path prev null ? cur : prev / cur; if (isDir) map.put(level, path); else if (ans null || path.length() ans.length()) ans path; i j 1; } return ans null ? 0 : ans.length(); } }逐行拆解代码片段作用细节说明while (i n s.charAt(i) \t level 0) i;统计前缀\t数量得到level并把i推进到名字开头level 0是一个恒真条件用于在循环条件里顺带自增level内层while (j n s.charAt(j) ! \n)从i开始扫描到本行结尾中途若出现.则isDir false说明这是一个文件而非目录cur s.substring(i, j)取出条目名不含前导制表符也不含换行符prev map.getOrDefault(level - 1, null)取父级level - 1的最新路径前缀若为null说明当前条目在根目录层级 0path prev null ? cur : prev / cur拼接完整路径层与层之间用/连接if (isDir) map.put(level, path);更新层级level的最新目录前缀只记录目录不记录文件else if (...path.length() ans.length()) ans path;文件则参与最长路径竞争用字符串存ans是为了便于演示输出具体路径时间复杂度与空间复杂度时间复杂度$O(n)$—— 每个字符至多被扫描常数次整体单次线性遍历。空间复杂度$O(n)$—— 哈希表最多存 $O(n)$ 个层级前缀同时ans中可能暂存最长的路径字符串最坏情况下路径长度接近 $n$。一个需要注意的判定细节判断是文件还是目录的逻辑是扫描条目过程中是否出现过.。因为文件名严格遵循name.extension格式所以只要条目名里含有.就是文件否则就是目录。这也解释了示例 3 中a返回 0它没有.是目录。同时要注意目录名也可能由字母、数字和/或空格组成不能出现点。解法二优化版——只记录路径长度解法一保存完整路径是为了方便输出具体方案。但题目只关心最终路径长度并不关心路径本身因此可以修改为只记录长度、不记录路径从而避免字符串拼接带来的消耗每次拼接prev / cur都会产生新的字符串对象利用s.length 10^4的数据范围用定长数组替代常数较大的哈希表。class Solution { static int[] hash new int[10010]; public int lengthLongestPath(String s) { Arrays.fill(hash, -1); int n s.length(), ans 0; for (int i 0; i n; ) { int level 0; while (i n s.charAt(i) \t level 0) i; int j i; boolean isDir true; while (j n s.charAt(j) ! \n) { if (s.charAt(j) .) isDir false; } Integer cur j - i; Integer prev level - 1 0 ? hash[level - 1] : -1; Integer path prev 1 cur; if (isDir) hash[level] path; else if (path ans) ans path; i j 1; } return ans; } }长度递推的关键公式与原解法相比这里发生了两个关键变换cur从字符串变成纯长度j - i条目名字符数完整路径长度由公式直接算出path prev 1 cur。其中1是路径分隔符/的贡献prev是父级路径长度若父级不存在即level - 1 0位于根目录则取-1此时path -1 1 cur cur恰好等于根目录下路径就是名字本身的长度与示例 4 的语义完全吻合。复杂度对比指标解法一模拟 哈希表解法二数组 只记长度时间复杂度$O(n)$$O(n)$空间复杂度$O(n)$$O(C)$$C 10^4 10$ 的定长数组即 $O(1)$ 量级额外字符串拼接有每层拼接产生新对象无全程只做整数运算能否输出具体路径能ans存的是路径字符串不能只返回长度边界情况与易错点小结无文件返回 0整个输入可能全是目录如示例 3 的a此时ans保持为null/0必须返回 0 而非目录路径长度。根目录level 0下的文件其路径就是文件名本身长度公式中prev -1的设计保证了这一点对应示例 4。.的判定只有文件名里允许出现.因此只要条目含.即判定为文件。不要把a.txt当作目录也不要假设目录名可以含点。\t计数与越界i、j的推进必须保证不越出[0, n)循环末尾i j 1可能恰好等于n此时外层循环自然结束。同一层级的覆盖更新同一层级可能出现多个目录例如subdir1与subdir2同为 level 1哈希表/数组始终只保留最新的那个目录前缀这是前序遍历 只关心最新兄弟这一性质决定的不能保留所有兄弟否则会拼接出错。从源码与仓库看这题的归类与延伸在本仓库中本题被同时收录于两大专题索引模拟.md —— 将其归入模拟类与 71. 简化路径中等Tag模拟、栈、385. 迷你语法分析器中等 等字符串解析类题目并列推荐指数均为 量级哈希表.md —— 将其归入哈希表类强调用哈希表维护层级前缀这一数据结构用法。这种双 Tag 归类是刻意设计的外层是模拟按格式逐段解析字符串内层是哈希表记录每层最新路径。阅读时建议与 71. 简化路径 对照——两者都在处理用文本表达的文件系统路径但 71 题是从路径字符串规范化388 题是从缩进文本还原层级一个做路径的化简、一个做路径的重建正好构成路径类模拟题的两个方向。举一反三把套路迁移到其他场景数前缀分隔符定层级 用哈希表/数组维护每层最新前缀的套路不止适用于本题缩进式文本还原树结构凡是输入以缩进表达层级的场景如目录树、缩进列表、YAML 风格文本的简化解析都可以先数缩进、再按层归属只看最新父级的滚动维护当前序遍历保证父先于子出现时每层只需保留最新条目哈希表/数组即可完成状态压缩从存完整答案到只存答案长度的优化当题目只要求长度/计数而不要求输出具体内容时应当把字符串拼接替换为整数递推这往往是同类题从能过到更快更省的关键一步本题正是借此把空间从 $O(n)$ 降到 $O(C)$。小结本题是一道形式新颖、思路朴素的中等题本质是用\t计数还原树形层级用哈希表维护每层最新目录前缀从而在单次线性扫描中完成所有路径长度的统计。掌握了切分、定层、归属、拼接、比较这条主链路以及只存长度的优化技巧后这类文本化树结构的解析题便能一通百通。更多同类题解可继续翻阅仓库 Index 专题目录 中的模拟与哈希表章节。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0388「文件的最长绝对路径」栈模拟全解析AlgoNote 算法通关手册LeetCode 0388「文件的最长绝对路径」栈模拟全解析 本篇技术指南围绕 AlgoNote 仓库中 LeetCode 03教程文档知识库LeetCode 409 最长回文串哈希表计数与回文构造条件的完整解析LeetCode-Book 题解LeetCode 409 最长回文串哈希表计数与回文构造条件的完整解析LeetCode Book 题解 导读 本题来自《Krahets 笔面试精选 88示例工程内存文件系统设计详解树 哈希表的两种建模方式LeetCode 588内存文件系统设计详解树 哈希表的两种建模方式LeetCode 588 本文围绕 LeetCode 588「Design an In Memory Fi示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考