文件的最长绝对路径
难度:
标签:
题目描述
假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：
这里将 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 <= 104input可能包含小写或大写的英文字母，一个换行符'\n'，一个制表符'\t'，一个点'.'，一个空格' '，和数字。
代码结果
运行时间: 23 ms, 内存: 16.1 MB
/*
* 思路：
* 使用Java Stream API来简化处理流程。
* 1. 将输入按换行符分割成行。
* 2. 使用map方法计算每行的深度和当前路径长度。
* 3. 通过reduce方法找到最大路径长度。
*/
import java.util.Arrays;
import java.util.List;
public class Solution {
public int lengthLongestPath(String input) {
return Arrays.stream(input.split("\\n"))
.mapToInt(line -> {
int depth = line.lastIndexOf("\t") + 1;
int len = line.length() - depth;
return new int[]{depth, len};
})
.reduce(new int[]{0}, (acc, cur) -> {
int depth = cur[0], len = cur[1];
if (depth > 0) {
acc[depth] = acc[depth - 1] + len + 1;
} else {
acc[0] = len;
}
if (input.split("\\n")[depth].contains(".")) {
acc[0] = Math.max(acc[0], acc[depth]);
}
return acc;
}, (a, b) -> a)[0];
}
}解释
方法:
该题解使用栈来模拟文件系统的目录结构。遍历输入字符串的每一行，根据行首的制表符数量确定当前目录/文件的缩进级别。如果当前行表示一个文件（包含扩展名），则计算该文件的绝对路径长度，并更新最长路径长度。如果当前行表示一个目录，则将其加入栈中，以便后续构建完整的目录路径。通过不断调整栈的大小和计算文件的绝对路径长度，最终得到文件系统中指向文件的最长绝对路径的长度。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
如何确定每行的缩进级别是根据制表符数量还是其他特征？
▷🦆
如何处理文件名或目录名中意外包含制表符或换行符的情况？
▷🦆
在实际使用中，栈的最大深度是否有可能超过输入字符串的行数？
▷🦆
解题思路中提到的字符串拼接操作，这种方法在处理极大数据量时是否会影响性能？
▷