栈题目：文件的最长绝对路径

题目

标题和出处

标题：文件的最长绝对路径

出处：388. 文件的最长绝对路径

难度

7 级

题目描述

要求

假设有一个文件系统存储文件和目录。一个文件系统的例子如下图所示：

这里将 $\text{dir}$ 作为根目录中的唯一目录。$\text{dir}$ 包含两个子目录 $\text{subdir1}$ 和 $\text{subdir2}$。$\text{subdir1}$ 包含文件 $\text{file1.ext}$ 和子目录 $\text{subsubdir1}$；$\text{subdir2}$ 包含子目录 $\text{subsubdir2}$，该子目录下包含文件 $\text{file2.ext}$。

在文本格式中，如下所示（* 表示制表符）：

dir
* subdir1
* * file1.ext
* * subsubdir1
* subdir2
* * subsubdir2
* * * file2.ext

如果是代码表示，上面的文件系统可以写为 $\text{"dir}\backslash \text{n}\backslash \text{tsubdir1}\backslash \text{n}\backslash \text{tfile1.ext}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir1}\backslash \text{n}\backslash \text{tsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{t}\backslash \text{tfile2.ext"}$。其中 $\text{‘}\backslash \text{n’}$ 和 $\text{‘}\backslash \text{t’}$ 分别是换行符和制表符。

文件系统中的每个文件和文件夹都有一个唯一的绝对路径，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 $\text{‘/’}$ 连接。上面例子中，指向 $\text{file2.ext}$ 的绝对路径是 $\text{"dir/subdir2/subsubdir2/file2.ext"}$。每个目录名由字母、数字和/或空格组成，每个文件名遵循 $\text{name.extension}$ 的格式，其中名称和扩展名由字母、数字和/或空格组成。

给定一个以上述格式表示文件系统的字符串 $\text{input}$，返回文件系统中指向文件的最长绝对路径的长度。如果系统中没有文件，返回 $\text{0}$。

示例

示例 1：

输入：$\text{input = "dir}\backslash \text{n}\backslash \text{tsubdir1}\backslash \text{n}\backslash \text{tsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{tfile.ext"}$
输出：$\text{20}$
解释：只有一个文件，绝对路径为 $\text{"dir/subdir2/file.ext"}$，路径长度 $\text{20}$。

示例 2：

输入：$\text{input = "dir}\backslash \text{n}\backslash \text{tsubdir1}\backslash \text{n}\backslash \text{t}\backslash \text{tfile1.ext}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir1}\backslash \text{n}\backslash \text{tsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{t}\backslash \text{tfile2.ext"}$
输出：$\text{32}$
解释：存在两个文件：
$\text{"dir/subdir1/file1.ext"}$，路径长度 $\text{21}$。
$\text{"dir/subdir2/subsubdir2/file2.ext"}$，路径长度 $\text{32}$。
返回 $\text{32}$，因为这是最长的路径。

示例 3：

输入：$\text{input = "a"}$
输出：$\text{0}$
解释：不存在任何文件。

示例 4：

输入：$\text{input = "file1.txt}\backslash \text{nfile2.txt}\backslash \text{nlongfile.txt"}$
输出：$\text{12}$
解释：根目录下有 $\text{3}$ 个文件。
因为根目录中任何东西的绝对路径都是名称本身，所以答案是 $\text{"longfile.txt"}$，路径长度为 $\text{12}$。

数据范围

• $\text{1}\le \text{input.length}\le {\text{10}}^{\text{4}}$
• $\text{input}$ 可能包含小写或大写的英语字母、换行符 $\text{‘}\backslash \text{n’}$、制表符 $\text{‘}\backslash \text{t’}$、点 $\text{‘.’}$、空格 $\text{‘ ’}$ 和数字

解法

思路和算法

由于文件系统中的每个文件和文件夹由换行符分隔，因此将给定的输入根据换行符分隔成字符串数组，字符串数组中的每个元素都是一个文件和文件夹，只需要处理字符串数组中的每个元素即可。

对于每个文件或文件夹，在字符串左端包含的制表符的数量即为该文件或文件夹所在的层级，第 $0$ 层为根目录下的文件或文件夹。如果一个文件或文件夹不在根目录下，则一定存在一个上级文件夹，上级文件夹的层级数为当前文件或文件夹的层级数减 $1$，且上级文件夹在字符串数组中的位置一定在当前文件或文件夹之前。

对于存在层级关系的文件系统，可以使用栈维护每一层的相对路径长度，同时计算每一层的绝对路径长度。由于栈内存储的是每一层的相对路径长度，因此栈内的每个元素所在位置反映了该元素表示的文件或文件夹所在的层数，当栈内有 $i$ 个元素时，栈顶的元素表示的是第 $i-1$ 层的文件或文件夹的相对路径长度。

依次遍历字符串数组中的每个元素，遍历过程中维护栈内元素和绝对路径长度，初始时栈为空，绝对路径长度为 $0$。具体做法如下：

1. 对于字符串数组中的当前元素，计算该字符串左端包含的制表符的数量，得到该文件或文件夹所在的层级和该文件或文件夹的相对路径长度；

2. 如果栈内元素个数大于当前层级，则将栈顶元素出栈，直到栈内元素个数等于当前层级，同时将出栈元素从绝对路径长度中减去；

3. 将当前的相对路径长度入栈，同时将当前的相对路径长度加到绝对路径长度；

4. 如果当前元素是文件，即字符串中包含点号，则根据当前的绝对路径长度更新文件的最长绝对路径长度。

在计算文件或文件夹的相对路径长度时，需要注意的一个细节是，除了根目录下的文件和文件夹以外，其余的每个文件和文件夹的相对路径都包含一个 $\text{‘/’}$，因此在计算文件和文件夹的相对路径长度时，根目录下的文件或文件夹的相对路径长度即为字符串的长度，非根目录下的文件或文件夹的相对路径长度为字符串的长度减去制表符个数加 $1$（加 $1$ 是因为包含一个 $\text{‘/’}$）。

遍历结束之后，即可得到文件的最长绝对路径长度。

代码

class Solution {
    
    public int lengthLongestPath(String input) {
    
        String[] array = input.split("\n");
        int maxPathLength = 0;
        int pathLength = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int arrayLength = array.length;
        for (int i = 0; i < arrayLength; i++) {
    
            String str = array[i];
            int level = 0;
            while (str.charAt(level) == '\t') {
    
                level++;
            }
            int length = str.length() - level + (level == 0 ? 0 : 1);
            while (stack.size() > level) {
    
                pathLength -= stack.pop();
            }
            stack.push(length);
            pathLength += length;
            if (str.indexOf('.') >= 0) {
    
                maxPathLength = Math.max(maxPathLength, pathLength);
            }
        }
        return maxPathLength;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $\text{input}$ 的长度。需要遍历字符串数组一次，原始输入中的每个字符的操作时间都是 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是字符串 $\text{input}$ 的长度。空间复杂度主要取决于字符串数组和栈，空间复杂度为 $O(n)$。