摘要

这道题其实挺有意思的，它要求我们解析一个用字符串表示的文件系统，然后找到指向文件的最长绝对路径。听起来像是文件系统操作，但实际上是一个字符串解析和路径计算的问题。关键点在于如何正确解析制表符（\t）来表示目录层级，以及如何计算每个文件的绝对路径长度。

这道题的核心在于如何理解制表符的层级关系，以及如何维护当前路径的栈结构。今天我们就用 Swift 来搞定这道题，顺便聊聊这种路径解析的方法在实际开发中的应用场景，比如文件系统操作、日志解析、配置文件解析等等。

描述

题目要求是这样的：给定一个用字符串表示的文件系统，其中 \n 表示换行符，\t 表示制表符（用来表示目录层级），返回文件系统中指向文件的最长绝对路径的长度。如果系统中没有文件，返回 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^4
• input 可能包含小写或大写的英文字母，一个换行符 '\n'，一个制表符 '\t'，一个点 '.'，一个空格 ' '，和数字。

这道题的核心思路是什么呢？我们需要按行分割字符串，然后解析每行的制表符数量来确定层级，使用栈来维护当前路径，最后计算每个文件的绝对路径长度，找到最长的。

题解答案

下面是完整的 Swift 解决方案：

class Solution {
    func lengthLongestPath(_ input: String) -> Int {
        // 按换行符分割字符串
        let lines = input.components(separatedBy: "\n")
        
        // 用栈来维护当前路径，存储每层的路径长度
        var stack: [Int] = []
        var maxLength = 0
        
        for line in lines {
            // 计算当前行的层级（制表符的数量）
            let level = getLevel(line)
            
            // 移除制表符，获取实际内容
            let content = line.replacingOccurrences(of: "\t", with: "")
            let contentLength = content.count
            
            // 如果当前层级小于等于栈的深度，需要弹出栈顶元素直到层级匹配
            while stack.count > level {
                stack.removeLast()
            }
            
            // 计算当前路径的长度
            // 如果栈为空，说明是根目录，路径长度就是内容长度
            // 如果栈不为空，需要加上父路径长度和分隔符 '/'
            let currentLength: Int
            if stack.isEmpty {
                currentLength = contentLength
            } else {
                currentLength = stack.last! + 1 + contentLength  // +1 是分隔符 '/'
            }
            
            // 如果是文件（包含 '.'），更新最大长度
            if content.contains(".") {
                maxLength = max(maxLength, currentLength)
            } else {
                // 如果是目录，将当前路径长度压入栈
                stack.append(currentLength)
            }
        }
        
        return maxLength
    }
    
    // 计算行的层级（制表符的数量）
    private func getLevel(_ line: String) -> Int {
        var level = 0
        for char in line {
            if char == "\t" {
                level += 1
            } else {
                break
            }
        }
        return level
    }
}

题解代码分析

让我们一步步分析这个解决方案：

1. 字符串分割

首先，我们需要将输入字符串按换行符分割成多行：

let lines = input.components(separatedBy: "\n")

components(separatedBy: "\n") 会将字符串按换行符分割成数组，每一行代表文件系统中的一个条目（文件或目录）。

2. 使用栈维护路径

我们使用栈来维护当前路径的层级结构：

var stack: [Int] = []

栈中存储的是每一层的路径长度（不包括当前层的名称）。这样我们可以快速计算当前路径的总长度。

为什么使用栈？

因为文件系统是树形结构，当我们进入一个目录时，需要记录当前路径；当我们退出目录时，需要回到上一级路径。栈的先进后出特性正好符合这种需求。

3. 计算层级

我们需要计算每行的层级，也就是制表符的数量：

private func getLevel(_ line: String) -> Int {
    var level = 0
    for char in line {
        if char == "\t" {
            level += 1
        } else {
            break
        }
    }
    return level
}

这个方法从字符串开头开始，统计连续的制表符数量。制表符的数量就代表了目录的层级深度。

示例：

• "dir" → level = 0（根目录）
• "\tsubdir1" → level = 1（一级子目录）
• "\t\tfile1.ext" → level = 2（二级子目录下的文件）

4. 处理路径栈

当我们处理新的一行时，需要根据层级调整栈：

// 如果当前层级小于等于栈的深度，需要弹出栈顶元素直到层级匹配
while stack.count > level {
    stack.removeLast()
}

这个逻辑很重要。如果当前行的层级小于栈的深度，说明我们已经回到了上一级或更上级的目录，需要弹出栈顶元素，直到栈的深度等于当前层级。

示例：

假设栈中存储的是 [3, 11, 20]（对应路径 “dir/subdir1/subsubdir1”），当前行是 "\tsubdir2"（level = 1）。

• 栈的深度是 3，当前层级是 1
• 需要弹出 2 个元素，栈变成 [3]
• 这样栈就对应路径 “dir”，符合当前层级

5. 计算当前路径长度

计算当前路径的总长度：

let currentLength: Int
if stack.isEmpty {
    currentLength = contentLength
} else {
    currentLength = stack.last! + 1 + contentLength  // +1 是分隔符 '/'
}

如果栈为空，说明是根目录，路径长度就是内容长度。如果栈不为空，需要加上父路径长度和分隔符 '/'。

示例：

假设栈中存储的是 [3]（对应路径 “dir”），当前内容是 "subdir1"（长度 7）。

• 当前路径长度 = 3（“dir”） + 1（‘/’） + 7（“subdir1”） = 11
• 对应路径 “dir/subdir1”

6. 判断文件和目录

我们需要判断当前条目是文件还是目录：

if content.contains(".") {
    maxLength = max(maxLength, currentLength)
} else {
    stack.append(currentLength)
}

如果内容包含 '.'，说明是文件，我们更新最大长度。如果是目录，我们将当前路径长度压入栈，供后续使用。

为什么用 '.' 判断？

根据题目描述，文件名遵循 name.extension 的格式，所以包含 '.' 的就是文件。目录名不包含 '.'。

7. 完整执行流程示例

让我们用一个例子来理解整个执行过程。假设输入是 "dir\n\tsubdir1\n\t\tfile1.ext\n\tsubdir2\n\t\tfile2.ext"：

1. 处理 “dir”：

   • level = 0，content = “dir”，contentLength = 3
   • 栈为空，currentLength = 3
   • 是目录，压入栈：stack = [3]

2. 处理 “\tsubdir1”：

   • level = 1，content = “subdir1”，contentLength = 7
   • 栈深度 = 1，等于 level，不需要弹出
   • currentLength = 3 + 1 + 7 = 11
   • 是目录，压入栈：stack = [3, 11]

3. 处理 “\t\tfile1.ext”：

   • level = 2，content = “file1.ext”，contentLength = 9
   • 栈深度 = 2，等于 level，不需要弹出
   • currentLength = 11 + 1 + 9 = 21
   • 是文件，更新 maxLength = 21

4. 处理 “\tsubdir2”：

   • level = 1，content = “subdir2”，contentLength = 7
   • 栈深度 = 2，大于 level，弹出栈顶：stack = [3]
   • currentLength = 3 + 1 + 7 = 11
   • 是目录，压入栈：stack = [3, 11]

5. 处理 “\t\tfile2.ext”：

   • level = 2，content = “file2.ext”，contentLength = 9
   • 栈深度 = 2，等于 level，不需要弹出
   • currentLength = 11 + 1 + 9 = 21
   • 是文件，更新 maxLength = max(21, 21) = 21

最终返回 21。

示例测试及结果

让我们用几个例子来测试一下这个解决方案：

示例 1：input = “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”

执行过程：

1. 处理 “dir”：栈 = [3]，maxLength = 0
2. 处理 “\tsubdir1”：栈 = [3, 11]，maxLength = 0
3. 处理 “\tsubdir2”：栈 = [3, 11]，弹出后栈 = [3]，然后栈 = [3, 11]，maxLength = 0
4. 处理 “\t\tfile.ext”：currentLength = 11 + 1 + 9 = 21，maxLength = 21

**结果：**返回 20（注意：实际路径是 “dir/subdir2/file.ext”，长度是 20，不是 21）

让我重新计算："dir/subdir2/file.ext" = 3 + 1 + 7 + 1 + 9 = 20

示例 2：input = “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”

执行过程：

1. 处理 “dir”：栈 = [3]
2. 处理 “\tsubdir1”：栈 = [3, 11]
3. 处理 “\t\tfile1.ext”：currentLength = 11 + 1 + 9 = 21，maxLength = 21
4. 处理 “\t\tsubsubdir1”：栈 = [3, 11, 21]
5. 处理 “\tsubdir2”：栈 = [3, 11]，弹出后栈 = [3]，然后栈 = [3, 11]
6. 处理 “\t\tsubsubdir2”：栈 = [3, 11, 21]
7. 处理 “\t\t\tfile2.ext”：currentLength = 21 + 1 + 9 = 31，maxLength = 31

**结果：**返回 32（路径 “dir/subdir2/subsubdir2/file2.ext” 的长度）

让我重新计算："dir/subdir2/subsubdir2/file2.ext" = 3 + 1 + 7 + 1 + 10 + 1 + 9 = 32

示例 3：input = “a”

执行过程：

1. 处理 “a”：level = 0，content = “a”，不包含 ‘.’，是目录
2. 栈 = [1]，maxLength = 0

**结果：**返回 0（没有文件）

示例 4：input = “file1.txt\nfile2.txt\nlongfile.txt”

执行过程：

1. 处理 “file1.txt”：currentLength = 9，maxLength = 9
2. 处理 “file2.txt”：currentLength = 9，maxLength = 9
3. 处理 “longfile.txt”：currentLength = 12，maxLength = 12

**结果：**返回 12

时间复杂度

让我们分析一下这个算法的时间复杂度：

时间复杂度：O(n)

其中 n 是输入字符串的长度。

分析：

1. 字符串分割：components(separatedBy: "\n") 需要遍历整个字符串一次，时间复杂度 O(n)
2. 遍历所有行：需要遍历所有行，总字符数不超过 n，时间复杂度 O(n)
3. 计算层级：每行最多有 O(n) 个字符，但所有行的总字符数是 n，所以总时间复杂度 O(n)
4. 栈操作：每个元素最多入栈和出栈一次，总操作次数不超过行数，时间复杂度 O(n)

所以总时间复杂度是 O(n)，这是最优的，因为我们至少需要遍历一次字符串来解析它。

对于题目约束（input.length <= 10^4），这个时间复杂度是完全可接受的。

空间复杂度

让我们分析一下这个算法的空间复杂度：

空间复杂度：O(n)

其中 n 是输入字符串的长度。

分析：

1. 字符串分割：lines 数组最多存储 O(n) 个字符，空间复杂度 O(n)
2. 栈：栈的深度最多等于目录的最大层级深度。在最坏情况下（比如所有目录都是单层嵌套），栈的深度是 O(n)
3. 临时变量：其他临时变量占用 O(1) 空间

所以总空间复杂度是 O(n)，这是必要的，因为我们需要存储解析后的数据。

实际应用场景

这种路径解析的方法在实际开发中应用非常广泛：

场景一：文件系统操作

在文件系统操作中，我们经常需要解析文件路径，计算路径长度等：

func getLongestFilePath(_ fileSystem: String) -> String? {
    // 解析文件系统字符串，找到最长路径
    let solution = Solution()
    let maxLength = solution.lengthLongestPath(fileSystem)
    // 返回最长路径
    return findPathWithLength(fileSystem, length: maxLength)
}

这种场景在文件管理器、备份工具等应用中经常用到。

场景二：日志解析

在日志解析中，我们可能需要解析带有层级结构的日志：

func parseHierarchicalLog(_ log: String) -> [LogEntry] {
    let lines = log.components(separatedBy: "\n")
    var stack: [LogEntry] = []
    var entries: [LogEntry] = []
    
    for line in lines {
        let level = getLevel(line)
        let content = line.replacingOccurrences(of: "\t", with: "")
        
        while stack.count > level {
            stack.removeLast()
        }
        
        let entry = LogEntry(content: content, level: level, parent: stack.last)
        entries.append(entry)
        
        if entry.isContainer {
            stack.append(entry)
        }
    }
    
    return entries
}

这种场景在日志分析工具、调试工具等应用中经常用到。

场景三：配置文件解析

在配置文件解析中，我们可能需要解析带有缩进的配置文件：

func parseIndentedConfig(_ config: String) -> ConfigNode {
    let lines = config.components(separatedBy: "\n")
    var stack: [ConfigNode] = []
    let root = ConfigNode(name: "root", children: [])
    stack.append(root)
    
    for line in lines {
        let level = getIndentLevel(line)
        let content = line.trimmingCharacters(in: .whitespaces)
        
        while stack.count > level + 1 {
            stack.removeLast()
        }
        
        let node = ConfigNode(name: content, children: [])
        stack.last?.children.append(node)
        
        if node.isSection {
            stack.append(node)
        }
    }
    
    return root
}

这种场景在配置管理、数据解析等应用中经常用到。

场景四：树形结构解析

在树形结构解析中，我们经常需要处理带有缩进的数据：

func parseTreeStructure(_ data: String) -> TreeNode {
    let lines = data.components(separatedBy: "\n")
    var stack: [TreeNode] = []
    let root = TreeNode(value: "root")
    stack.append(root)
    
    for line in lines {
        let level = getLevel(line)
        let value = line.replacingOccurrences(of: "\t", with: "")
        
        while stack.count > level + 1 {
            stack.removeLast()
        }
        
        let node = TreeNode(value: value)
        stack.last?.children.append(node)
        stack.append(node)
    }
    
    return root
}

这种场景在数据可视化、树形结构展示等应用中经常用到。

总结

这道题虽然看起来复杂，但实际上是一个经典的栈应用问题。通过使用栈来维护路径层级，我们可以清晰地处理各种情况。

关键点总结：

1. 栈的应用：使用栈来维护当前路径的层级结构
2. 层级计算：通过制表符数量来确定目录层级
3. 路径长度计算：通过栈中存储的路径长度来快速计算当前路径长度
4. 文件判断：通过是否包含 '.' 来判断是文件还是目录

算法优势：

1. 时间复杂度低：只需要遍历字符串一次，O(n)
2. 实现简单：逻辑清晰，容易理解和维护
3. 扩展性好：可以很容易地扩展到处理更复杂的文件系统结构

实际应用：

路径解析的方法在很多场景中都有应用，比如文件系统操作、日志解析、配置文件解析、树形结构解析等。理解这种解析技术，不仅能帮助我们解决类似的算法题，还能让我们更好地处理各种层级结构的数据。