文件的最长绝对路径

难度: Medium

假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：

这里将 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⁴
input 可能包含小写或大写的英文字母，一个换行符 '\n'，一个制表符 '\t'，一个点 '.'，一个空格 ' '，和数字。

Submission

运行时间: 23 ms

内存: 16.1 MB

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        stack = []  # 用于存储目录路径的栈
        max_length = 0  # 最长路径长度
        
        # 将输入字符串按换行符分割成多行
        lines = input.split('
')
        
        for line in lines:
            # 计算当前行的缩进级别（制表符数量）
            level = line.count('\t')
            
            # 根据缩进级别调整栈的大小
            while len(stack) > level:
                stack.pop()
            
            # 去除行首的制表符，得到当前目录/文件名
            name = line.lstrip('\t')
            
            # 如果当前行表示一个文件（包含扩展名），则计算绝对路径长度并更新最大长度
            if '.' in name:
                path = '/'.join(stack + [name])
                max_length = max(max_length, len(path))
            else:
                # 如果当前行表示一个目录，则将其加入栈中
                stack.append(name)
        
        return max_length

Explain

该题解使用栈来模拟文件系统的目录结构。遍历输入字符串的每一行，根据行首的制表符数量确定当前目录/文件的缩进级别。如果当前行表示一个文件（包含扩展名），则计算该文件的绝对路径长度，并更新最长路径长度。如果当前行表示一个目录，则将其加入栈中，以便后续构建完整的目录路径。通过不断调整栈的大小和计算文件的绝对路径长度，最终得到文件系统中指向文件的最长绝对路径的长度。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        stack = []  # 用于存储目录路径的栈
        max_length = 0  # 最长路径长度
        
        # 将输入字符串按换行符分割成多行
        lines = input.split('
')
        
        for line in lines:
            # 计算当前行的缩进级别（制表符数量）
            level = line.count('\t')
            
            # 根据缩进级别调整栈的大小
            while len(stack) > level:
                stack.pop()
            
            # 去除行首的制表符，得到当前目录/文件名
            name = line.lstrip('\t')
            
            # 如果当前行表示一个文件（包含扩展名），则计算绝对路径长度并更新最大长度
            if '.' in name:
                path = '/'.join(stack + [name])
                max_length = max(max_length, len(path))
            else:
                # 如果当前行表示一个目录，则将其加入栈中
                stack.append(name)
        
        return max_length

Explore

在本题的解题思路中，每行的缩进级别是通过计算行首的制表符数量来确定的。这是因为在类似文件系统的结构中，制表符通常用于表示不同级别的目录深度。没有使用其他特征来确定缩进级别，因为题目描述和常见的文件系统表示法都假定缩进使用制表符来体现。

题解中并没有直接处理文件名或目录名中包含制表符或换行符的情况。在实际应用中，这种情况需要额外的逻辑来处理。例如，可以在处理之前先清洗输入数据，去除或替换文件名中的制表符和换行符。如果题目允许错误输入，需要定义一个更复杂的解析机制来准确区分各级目录和文件名。

在实际使用中，栈的最大深度不会超过输入字符串的行数。栈的深度直接对应于目录的级别，且每个目录或文件至少占据一行。因此，栈的深度最大值等于行的数量，即每行代表一个新的目录层级。

是的，字符串拼接操作在处理大量数据时可能会影响性能。在Python中，每次使用 '+' 运算符拼接字符串时，都会创建一个新的字符串对象，这会导致大量的内存分配和复制，从而影响性能。尤其是在目录层级较深且文件名较长的情况下，重复的字符串拼接操作会显著增加时间和空间复杂度。一个更高效的方法可能是使用字符串列表和在最终输出前一次性使用 'join' 方法来连接，这样可以减少中间字符串的创建和销毁。