O(n) time O(n) space stack solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public int lengthLongestPath(String input) {
String[] lines = input.split("\n");
Stack<Integer> path = new Stack<>();
path.push(0);
int max = 0;

for (String line : lines) {
int tabIndex = line.lastIndexOf("\t") + 1;
while (path.size() - 1 > tabIndex) {
path.pop();
}
int length = path.peek() + 1 + line.length() - tabIndex;
path.push(length);
if (line.indexOf(".") != -1)
max = Math.max(max, length - 1);
}

return max;
}
}

O(n) time O(n) DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int lengthLongestPath(String input) {
String[] lines = input.split("\n");
int[] length = new int[lines.length + 1];
int max = 0;

for (String line : lines) {
int depth = line.lastIndexOf("\t") + 1;
length[depth + 1] = length[depth] + 1 + line.length() - depth;
if (line.indexOf(".") != -1) {
max = Math.max(max, length[depth + 1] - 1);
}
}
return max;
}
}