0388. Longest Absolute File Path ================================ 题目信息 -------- :题号: 0388 :难度: Medium :主题: 文件系统文本、层级、绝对路径、最大字符长度 :原题: `LeetCode 0388 `_ :重点: 换行分隔条目、前导制表符表示深度、名称含点视为文件、路径分隔符计入长度、没有文件返回 0 题目重述 -------- 字符串 ``input`` 编码一个文件系统。不同文件或目录条目由换行符 ``\n`` 分隔;某条目开头连续的制表符 ``\t`` 数量表示它相对根层的深度。名称中包含点号 ``.`` 的条目视为文件,其余条目视为目录。 文件的绝对路径由从根目录到该文件的各级名称使用 ``/`` 连接。返回所有文件绝对路径中的最大字符长度,分隔符也计入长度;若表示中没有任何文件,返回 ``0``。``input`` 长度位于 ``[1, 10^4]``,每个文件或目录名称非空,输入保证层级表示有效。 自建示例 -------- 最深文件形成最长路径: .. code-block:: text 输入:input = "root\n\tlogs\n\t\ta.txt\n\tdata\n\t\tarchive\n\t\t\tb.bin" 输出:23 解释:最长路径是 "root/data/archive/b.bin",四段名称和三个斜杠共 23 个字符。 只有目录: .. code-block:: text 输入:input = "home\n\tdocs\n\timages" 输出:0 解释:没有任何名称包含点号,因此文件系统中没有文件路径可统计。 用每一层的累计路径长度压缩树结构 ---------------------------------- 逐行读取条目,前导制表符数量就是深度。维护 ``pathLength[depth]``,表示到该层条目父目录为止的路径长度;当前条目长度等于父路径长度加一个斜杠(若有父层)再加名称长度。目录只更新这一层的长度,文件则用当前累计长度更新答案,不再把文件作为后续目录父节点。 遇到更浅层条目时,覆盖对应深度的长度即可丢弃旧的兄弟分支;因为输入按先序层级排列,当前行的父目录信息总在数组中。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int lengthLongestPath(std::string input) { std::vector pathLength(1, 0); int answer = 0; int start = 0; while (start < static_cast(input.size())) { int end = input.find('\n', start); if (end == static_cast(std::string::npos)) { end = static_cast(input.size()); } int depth = 0; while (start + depth < end && input[start + depth] == '\t') { ++depth; } std::string name = input.substr( start + depth, end - start - depth); int currentLength = pathLength[depth] + (depth == 0 ? 0 : 1) + static_cast(name.size()); if (name.find('.') != std::string::npos) { answer = std::max(answer, currentLength); } else { if (pathLength.size() <= depth + 1) { pathLength.resize(depth + 2); } pathLength[depth + 1] = currentLength; } start = end + 1; } return answer; } }; 代码分析 -------- ``pathLength[depth]`` 始终是当前条目的父路径长度,斜杠只在有父目录时计入;文件名中的点号直接决定是否更新答案。每个字符被扫描和切分有限次,时间复杂度为 ``O(|input|)``,额外空间为 ``O(h)``,``h`` 为层级深度。