388. 文件的最长绝对路径
题目描述
一个文件系统用字符串 input 描述。每个文件或目录占一行，行与行之间用换行符 \n 隔开。行首制表符 \t 的个数表示层级：没有 \t 的在最顶层，有 d 个 \t 的属于它上方最近一个 d - 1 层的目录。
名字里含有 . 的是文件，形如 name.extension；不含 . 的是目录。名字由字母、数字或空格组成。
某一项的绝对路径，是从最顶层开始逐级写出所在目录，最后写出它自己，中间用 / 连接，例如 "root/docs/a.txt"。顶层项的路径就是它的名字。
返回所有文件中最长的绝对路径的字符数。只考虑文件，不考虑目录。如果没有任何文件，返回 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
解释：两个文件路径长度分别为 21 和 32，取较长的 "dir/subdir2/subsubdir2/file2.ext"。
示例 3
输入：input = "a" 输出：0
解释：a 是目录，不存在文件。
数据范围
1 <= input.length <= 10^4input只可能包含大小写英文字母、数字、空格、.、\n和\t
解题思路
按行扫描，用栈记录当前目录链上每一层的路径长度。stack[d] 表示深度为 d 的节点的父目录路径长度（含末尾的 /），stack[0] = 0。遇到深度为 d 的行，先弹出栈直到长度为 d + 1，再算 cur = stack[-1] + len(name) + 1。文件就用 cur - 1 更新答案，目录就把 cur 压栈。
为什么正确
处理完一行后，栈中恰好是从根到当前目录这条链上各层的累计长度。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
必须在处理每一行前先把栈弹到深度 + 1，否则兄弟目录会接在前一个兄弟的路径后面；另外文件长度不含末尾 /，要减 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def lengthLongestPath(self, input: str) -> int:
stack = [0]
best = 0
for line in input.split('\n'):
depth = line.count('\t')
name = line[depth:]
while len(stack) > depth + 1:
stack.pop()
cur = stack[-1] + len(name) + 1
if '.' in name:
best = max(best, cur - 1)
else:
stack.append(cur)
return bestclass Solution {
public int lengthLongestPath(String input) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
int best = 0;
for (String line : input.split("\n")) {
int depth = line.length() - line.replace("\t", "").length();
String name = line.substring(depth);
while (stack.size() > depth + 1) {
stack.pop();
}
int cur = stack.peek() + name.length() + 1;
if (name.contains(".")) {
best = Math.max(best, cur - 1);
} else {
stack.push(cur);
}
}
return best;
}
}class Solution {
public:
int lengthLongestPath(string input) {
vector<int> stk = {0};
int best = 0;
stringstream ss(input);
string line;
while (getline(ss, line, '\n')) {
int depth = count(line.begin(), line.end(), '\t');
string name = line.substr(depth);
while ((int)stk.size() > depth + 1) {
stk.pop_back();
}
int cur = stk.back() + (int)name.size() + 1;
if (name.find('.') != string::npos) {
best = max(best, cur - 1);
} else {
stk.push_back(cur);
}
}
return best;
}
};func lengthLongestPath(input string) int {
stack := []int{0}
best := 0
for _, line := range strings.Split(input, "\n") {
depth := strings.Count(line, "\t")
name := line[depth:]
for len(stack) > depth+1 {
stack = stack[:len(stack)-1]
}
cur := stack[len(stack)-1] + len(name) + 1
if strings.Contains(name, ".") {
best = max(best, cur-1)
} else {
stack = append(stack, cur)
}
}
return best
}var lengthLongestPath = function(input) {
const stack = [0];
let best = 0;
for (const line of input.split('\n')) {
const depth = line.split('\t').length - 1;
const name = line.slice(depth);
while (stack.length > depth + 1) {
stack.pop();
}
const cur = stack[stack.length - 1] + name.length + 1;
if (name.includes('.')) {
best = Math.max(best, cur - 1);
} else {
stack.push(cur);
}
}
return best;
};function lengthLongestPath(input: string): number {
const stack: number[] = [0];
let best = 0;
for (const line of input.split('\n')) {
const depth = line.split('\t').length - 1;
const name = line.slice(depth);
while (stack.length > depth + 1) {
stack.pop();
}
const cur = stack[stack.length - 1] + name.length + 1;
if (name.includes('.')) {
best = Math.max(best, cur - 1);
} else {
stack.push(cur);
}
}
return best;
}