一、题目描述
假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：
这里将 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 <= 10^4input可能包含小写或大写的英文字母，一个换行符'\n'，一个制表符'\t'，一个点'.'，一个空格' '，和数字。
二、解题思路
- 使用栈来保存当前访问的目录或文件的名称。
- 按行遍历输入字符串，每行代表一个文件或目录。
- 通过计算每行的制表符数量来确定当前文件或目录的层级。
- 如果当前行的层级小于栈的大小，说明回到了上一个层级，需要从栈中弹出元素，直到栈的大小等于当前层级。
- 将当前行去除制表符和换行符后的字符串推入栈中。
- 如果当前行是一个文件（包含点号’.'），计算从根目录到当前文件的最长路径长度，并更新结果。
- 遍历结束后，返回结果。
三、具体代码
import java.util.*;public class Solution {public int lengthLongestPath(String input) {// 使用栈来保存当前路径的每一部分Stack<String> stack = new Stack<>();// 初始化最长路径长度为0int maxLen = 0;// 按行分割输入字符串String[] lines = input.split("\n");for (String line : lines) {// 计算当前行的层级，即制表符的数量int level = countTabs(line);// 将当前行去除制表符line = line.substring(level);// 如果当前层级小于栈的大小，说明回到了上一个层级，需要弹出栈顶元素while (stack.size() > level) {stack.pop();}// 将当前行推入栈中stack.push(line);// 如果当前行是文件，计算路径长度并更新最长路径长度if (line.contains(".")) {int currentLen = 0;for (String s : stack) {currentLen += s.length();}// 加上路径中目录之间的分隔符数量maxLen = Math.max(maxLen, currentLen + stack.size() - 1);}}return maxLen;}// 计算字符串中制表符的数量private int countTabs(String line) {int count = 0;while (count < line.length() && line.charAt(count) == '\t') {count++;}return count;}
}
这段代码定义了一个Solution类，其中包含一个lengthLongestPath方法，该方法实现了上述解题思路。countTabs是一个辅助方法，用于计算字符串中的制表符数量。
四、时间复杂度和空间复杂度
1. 时间复杂度
-
按行分割输入字符串：
input.split("\n")。这个操作的时间复杂度是 O(n)，其中 n 是输入字符串的长度，因为我们需要遍历整个字符串来找到所有的换行符。 -
遍历每一行：我们有一个循环，它会遍历输入字符串中的每一行。如果输入字符串中有 m 行，则这个循环的时间复杂度是 O(m)。
-
计算每一行的制表符数量：在循环内部，我们调用了
countTabs(line)方法。这个方法在最坏情况下的时间复杂度是 O(k)，其中 k 是行的长度。 -
弹出栈中的元素：在最坏情况下，如果每一行都是文件系统的根目录，那么我们需要弹出栈中的所有元素。这个操作的时间复杂度是 O(m)，因为可能需要弹出 m 个元素。
-
将当前行推入栈中：这个操作的时间复杂度是 O(1)。
-
检查当前行是否是文件并计算路径长度：在循环内部，如果当前行是文件，我们需要遍历栈中的所有元素来计算路径长度。在最坏情况下，这个操作的时间复杂度是 O(m)，因为栈可能包含 m 个元素。
综合以上分析，总的时间复杂度是 O(n + m * k + m * m)，其中 n 是输入字符串的长度，m 是行数，k 是行的平均长度。由于 m 和 k 通常与 n 成正比，因此可以简化为 O(n^2)。
2. 空间复杂度
-
栈空间：在最坏情况下，栈可能包含输入字符串中的所有行，因此空间复杂度是 O(m)，其中 m 是行数。
-
分割后的行数组：
input.split("\n")也会占用空间，空间复杂度是 O(m * k)，其中 m 是行数，k 是行的平均长度。
综合以上分析，总的空间复杂度是 O(m * k)，其中 m 是行数，k 是行的平均长度。由于 m 和 k 通常与输入字符串的长度 n 成正比，因此可以简化为 O(n)。
五、总结知识点
-
Java 类定义：
public class Solution：定义了一个公共类Solution。
-
方法定义：
public int lengthLongestPath(String input)：定义了一个公共方法lengthLongestPath，接受一个字符串参数input并返回一个整数。
-
数据结构：
Stack<String>：使用 Java 中的Stack类来存储目录和文件的名称。Stack是Vector的一个子类，用于实现后进先出（LIFO）的数据结构。
-
字符串操作：
input.split("\n")：使用split方法按换行符分割输入字符串，得到一个字符串数组。line.substring(level)：使用substring方法截取字符串，去除前导的制表符。
-
循环和条件语句：
for (String line : lines)：使用增强型for循环遍历字符串数组。while (stack.size() > level)：使用while循环来弹出栈顶元素，直到栈的大小与当前层级匹配。
-
字符操作：
line.charAt(count) == '\t'：使用charAt方法访问字符串中的单个字符，并检查它是否是制表符。
-
数学操作：
Math.max(maxLen, currentLen + stack.size() - 1)：使用Math.max方法来更新最长路径长度。
-
成员变量和局部变量：
int maxLen：定义了一个成员变量maxLen来存储最长路径的长度。int level、int count、int currentLen：定义了局部变量来在方法中存储临时状态和计算结果。
-
递归方法调用：
countTabs(line)：在主方法中调用了一个辅助方法countTabs来计算字符串中的制表符数量。
-
逻辑控制：
if (line.contains("."))：使用if语句检查当前行是否包含点号（.），从而判断它是否是文件。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
