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 由字母、数字和/或空格组成。
给定一个表示上述格式文件系统的字符串输入，返回抽象文件系统中文件的最长绝对路径的长度。如果系统中没有文件，返回 0。
注意测试用例保证文件系统是有效的，并且没有文件或目录名的长度为 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
解释：我们没有任何文件，只有一个名为 "a" 的目录。
提示：
1 <= input.length <= 10^4input可能包含小写或大写英文字母、换行符 ‘\n’、制表符 ‘\t’、点号 ‘.’、空格 ’ ’ 和数字。- 所有文件和目录名都有正长度。
解题思路
这道题的核心思路是使用栈模拟文件系统的层级结构。
问题分析：
- 通过制表符
\t的数量判断当前文件/目录的深度层级 - 只有文件（包含
.的名称）才需要计算路径长度，目录不算 - 需要维护从根目录到当前位置的路径长度
解题步骤：
- 按换行符分割输入字符串，得到每一行
- 对每一行：
- 统计前导制表符数量，确定层级深度
- 获取去除制表符后的名称
- 使用栈维护每一层的累计路径长度：
- 当前层级小于等于栈大小时，需要弹出多余层级
- 将当前层级的累计长度压入栈中
- 如果当前名称是文件（包含 ‘.’），更新最大路径长度
关键点：
- 栈中存储的是到达每一层的累计路径长度
- 路径长度包括分隔符
/的长度 - 最终答案是所有文件路径长度的最大值
这种方法时间复杂度为 O(n)，空间复杂度为 O(深度)，是最优解法。
代码实现
class Solution {
public:
int lengthLongestPath(string input) {
vector<int> stack;
int maxLen = 0;
// 按换行符分割字符串
stringstream ss(input);
string line;
while (getline(ss, line)) {
// 计算层级深度（制表符数量）
int level = 0;
while (level < line.size() && line[level] == '\t') {
level++;
}
// 获取名称（去除制表符）
string name = line.substr(level);
// 调整栈大小到当前层级
while (stack.size() > level) {
stack.pop_back();
}
// 计算当前路径长度
int currentLen = name.length();
if (!stack.empty()) {
currentLen += stack.back() + 1; // +1 for '/'
}
// 如果是文件，更新最大长度
if (name.find('.') != string::npos) {
maxLen = max(maxLen, currentLen);
} else {
// 如果是目录，压入栈
stack.push_back(currentLen);
}
}
return maxLen;
}
};
class Solution:
def lengthLongestPath(self, input: str) -> int:
stack = []
max_len = 0
# 按换行符分割
lines = input.split('\n')
for line in lines:
# 计算层级深度（制表符数量）
level = 0
while level < len(line) and line[level] == '\t':
level += 1
# 获取名称（去除制表符）
name = line[level:]
# 调整栈大小到当前层级
while len(stack) > level:
stack.pop()
# 计算当前路径长度
current_len = len(name)
if stack:
current_len += stack[-1] + 1 # +1 for '/'
# 如果是文件，更新最大长度
if '.' in name:
max_len = max(max_len, current_len)
else:
# 如果是目录，压入栈
stack.append(current_len)
return max_len
public class Solution {
public int LengthLongestPath(string input) {
var stack = new List<int>();
int maxLen = 0;
// 按换行符分割
string[] lines = input.Split('\n');
foreach (string line in lines) {
// 计算层级深度（制表符数量）
int level = 0;
while (level < line.Length && line[level] == '\t') {
level++;
}
// 获取名称（去除制表符）
string name = line.Substring(level);
// 调整栈大小到当前层级
while (stack.Count > level) {
stack.RemoveAt(stack.Count - 1);
}
// 计算当前路径长度
int currentLen = name.Length;
if (stack.Count > 0) {
currentLen += stack[stack.Count - 1] + 1; // +1 for '/'
}
// 如果是文件，更新最大长度
if (name.Contains('.')) {
maxLen = Math.Max(maxLen, currentLen);
} else {
// 如果是目录，压入栈
stack.Add(currentLen);
}
}
return maxLen;
}
}
var lengthLongestPath = function(input) {
const stack = [];
let maxLen = 0;
// 按换行符分割
const lines = input.split('\n');
for (const line of lines) {
// 计算层级深度（制表符数量）
let level = 0;
while (level < line.length && line[level]
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | n 是输入字符串的长度，需要遍历每个字符一次 |
| 空间复杂度 | O(d) | d 是文件系统的最大深度，栈最多存储 d 个层级的路径长度 |