My code:
public class Solution {
public int lengthLongestPath(String input) {
if (input == null || input.length() == 0){
return 0;
}
String[] parts = input.split("\n");
if (parts == null || parts.length == 0) {
return 0;
}
Stack<String> st = new Stack<String>();
int max = 0;
int counter = 0;
for (int i = 0; i < parts.length; i++) {
String s = parts[i];
int level = getLevel(s);
while (!st.isEmpty() && level <= st.size() - 1) {
String out = st.pop();
counter -= (out.length() + 1);
}
String removeT = s.replaceAll("\t", "");
st.push(removeT);
counter += removeT.length() + 1;
if (removeT.indexOf(".") != -1) {
max = Math.max(max, counter);
}
}
return max == 0 ? 0 : max - 1;
}
private int getLevel(String s) {
String temp = s.replaceAll("\t", "");
return s.length() - temp.length();
}
}
reference:
https://discuss.leetcode.com/topic/55088/java-o-n-solution-using-stack
一开始没思路，打算建树，用dfs来做。
后来想想放弃了，实在不知道，directory name 怎么规定的算一层。
然后看了答案，才知道，原来每个name 前面的 \t 个数不相同，可以拿这个来区分不同level的文件。
于是思路一下子清晰了。
比如：
dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext
dir: 0
subdir1: 1
subdir2: 1
file.ext: 2
数字表示前面 \t 的个数，正好也可以作为层数。
于是做一个栈。如果当前需要插进去的元素，他的level <= 栈顶元素的level，那么把栈顶的弹出去，直到满足条件为止。
然后在整个过程中，记录下栈里面所有字母的个数。
记住，栈里面存放的是整个路径，但是没有加上 ''
所以，每次插入的时候，我们给counter加时，都手动加个1，表示
当然， dir 是不需要 \ 的，所以，在最后返回结果的时候，如果max > 0, 那么 max - 1去掉这个不需要加 '' 的重复。
Anyway, Good luck, Richardo! -- 09/18/2016
