LeetCode 388: Longest Absolute File Path (Depth Stack + Prefix Length)
LeetCode 388StringStackToday we solve LeetCode 388 - Longest Absolute File Path.
Source: https://leetcode.com/problems/longest-absolute-file-path/
English
Problem Summary
Given a string that encodes a file system using \n and \t, return the length of the longest absolute path to a file. A file is identified by containing a dot . in its name.
Key Insight
For each line, count its depth by leading tabs. Maintain lenAtDepth[d] = total path length up to depth d (including slashes). Then current full length is lenAtDepth[d] + nameLen.
Algorithm
- Split by \n into entries.
- For each entry, count leading \t as depth d.
- Remove tabs to get name, compute curr = lenAtDepth[d] + name.length().
- If name is a file, update answer with curr.
- Else set lenAtDepth[d+1] = curr + 1 (extra slash for children).
Complexity Analysis
Let n be input length.
Time: O(n).
Space: O(n) in worst case for depth table.
Common Pitfalls
- Forgetting the slash when moving from directory to child.
- Treating every line as a file without checking dot.
- Using character count with tabs still included.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int lengthLongestPath(String input) {
String[] lines = input.split("\\n");
int[] lenAtDepth = new int[lines.length + 1];
int ans = 0;
for (String line : lines) {
int depth = 0;
while (depth < line.length() && line.charAt(depth) == '\\t') {
depth++;
}
String name = line.substring(depth);
int curr = lenAtDepth[depth] + name.length();
if (name.indexOf('.') != -1) {
ans = Math.max(ans, curr);
} else {
lenAtDepth[depth + 1] = curr + 1;
}
}
return ans;
}
}func lengthLongestPath(input string) int {
lines := strings.Split(input, "\n")
lenAtDepth := make([]int, len(lines)+1)
ans := 0
for _, line := range lines {
depth := 0
for depth < len(line) && line[depth] == '\t' {
depth++
}
name := line[depth:]
curr := lenAtDepth[depth] + len(name)
if strings.Contains(name, ".") {
if curr > ans {
ans = curr
}
} else {
lenAtDepth[depth+1] = curr + 1
}
}
return ans
}class Solution {
public:
int lengthLongestPath(string input) {
vector<int> lenAtDepth(input.size() + 1, 0);
int ans = 0;
int i = 0, n = input.size();
while (i < n) {
int depth = 0;
while (i < n && input[i] == '\t') {
depth++;
i++;
}
int start = i;
bool isFile = false;
while (i < n && input[i] != '\n') {
if (input[i] == '.') isFile = true;
i++;
}
int nameLen = i - start;
int curr = lenAtDepth[depth] + nameLen;
if (isFile) {
ans = max(ans, curr);
} else {
lenAtDepth[depth + 1] = curr + 1;
}
i++;
}
return ans;
}
};class Solution:
def lengthLongestPath(self, input: str) -> int:
lines = input.split("\n")
len_at_depth = [0] * (len(lines) + 1)
ans = 0
for line in lines:
depth = 0
while depth < len(line) and line[depth] == "\t":
depth += 1
name = line[depth:]
curr = len_at_depth[depth] + len(name)
if "." in name:
ans = max(ans, curr)
else:
len_at_depth[depth + 1] = curr + 1
return ans/**
* @param {string} input
* @return {number}
*/
var lengthLongestPath = function(input) {
const lines = input.split("\n");
const lenAtDepth = new Array(lines.length + 1).fill(0);
let ans = 0;
for (const line of lines) {
let depth = 0;
while (depth < line.length && line[depth] === "\t") {
depth++;
}
const name = line.slice(depth);
const curr = lenAtDepth[depth] + name.length;
if (name.includes(".")) {
ans = Math.max(ans, curr);
} else {
lenAtDepth[depth + 1] = curr + 1;
}
}
return ans;
};中文
题目概述
给定一个用 \n 和 \t 编码的文件系统字符串，返回某个文件的最长绝对路径长度。文件名特点是包含点号 .。
核心思路
统计每一行前导 \t 得到层级 d，维护 lenAtDepth[d] 表示到该层父路径的总长度（含斜杠）。当前节点总长度就是 lenAtDepth[d] + 名称长度。
算法步骤
- 用 \n 分割每个目录或文件项。
- 逐行数前导 \t，得到层级 d。
- 去掉前导 \t 后得到名字，计算 curr。
- 若包含 .，说明是文件，更新答案。
- 否则是目录，设置 lenAtDepth[d+1] = curr + 1 给子节点使用。
复杂度分析
设输入总长度为 n。
时间复杂度：O(n)。
空间复杂度：O(n)（最坏深度/行数场景）。
常见陷阱
- 忘记目录到子节点之间的 /。
- 没有用点号判断文件，导致目录也更新答案。
- 计算长度时把前导 \t 也算进去了。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int lengthLongestPath(String input) {
String[] lines = input.split("\\n");
int[] lenAtDepth = new int[lines.length + 1];
int ans = 0;
for (String line : lines) {
int depth = 0;
while (depth < line.length() && line.charAt(depth) == '\\t') {
depth++;
}
String name = line.substring(depth);
int curr = lenAtDepth[depth] + name.length();
if (name.indexOf('.') != -1) {
ans = Math.max(ans, curr);
} else {
lenAtDepth[depth + 1] = curr + 1;
}
}
return ans;
}
}func lengthLongestPath(input string) int {
lines := strings.Split(input, "\n")
lenAtDepth := make([]int, len(lines)+1)
ans := 0
for _, line := range lines {
depth := 0
for depth < len(line) && line[depth] == '\t' {
depth++
}
name := line[depth:]
curr := lenAtDepth[depth] + len(name)
if strings.Contains(name, ".") {
if curr > ans {
ans = curr
}
} else {
lenAtDepth[depth+1] = curr + 1
}
}
return ans
}class Solution {
public:
int lengthLongestPath(string input) {
vector<int> lenAtDepth(input.size() + 1, 0);
int ans = 0;
int i = 0, n = input.size();
while (i < n) {
int depth = 0;
while (i < n && input[i] == '\t') {
depth++;
i++;
}
int start = i;
bool isFile = false;
while (i < n && input[i] != '\n') {
if (input[i] == '.') isFile = true;
i++;
}
int nameLen = i - start;
int curr = lenAtDepth[depth] + nameLen;
if (isFile) {
ans = max(ans, curr);
} else {
lenAtDepth[depth + 1] = curr + 1;
}
i++;
}
return ans;
}
};class Solution:
def lengthLongestPath(self, input: str) -> int:
lines = input.split("\n")
len_at_depth = [0] * (len(lines) + 1)
ans = 0
for line in lines:
depth = 0
while depth < len(line) and line[depth] == "\t":
depth += 1
name = line[depth:]
curr = len_at_depth[depth] + len(name)
if "." in name:
ans = max(ans, curr)
else:
len_at_depth[depth + 1] = curr + 1
return ans/**
* @param {string} input
* @return {number}
*/
var lengthLongestPath = function(input) {
const lines = input.split("\n");
const lenAtDepth = new Array(lines.length + 1).fill(0);
let ans = 0;
for (const line of lines) {
let depth = 0;
while (depth < line.length && line[depth] === "\t") {
depth++;
}
const name = line.slice(depth);
const curr = lenAtDepth[depth] + name.length;
if (name.includes(".")) {
ans = Math.max(ans, curr);
} else {
lenAtDepth[depth + 1] = curr + 1;
}
}
return ans;
};
Comments