388. Longest Absolute File Path

三刷
本质上是dfs，走到leaf的时候update 结果
stack的作用是back track
99.90 %
class Solution {
    public int lengthLongestPath(String input) {
        if (input == null || input.length() == 0) {
            return 0;
        }
        int level = 0;
        int max = 0;
        int currLength = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        String[] dirs = input.split("\n");
        for (String dir : dirs) {
            level = dir.lastIndexOf("\t") + 1;
            while (deque.size() > level) {
                deque.removeFirst();
            }
            currLength = dir.length() + (deque.isEmpty() ? 0 : deque.peekFirst()) - level + 1;
            if (dir.contains(".")) {
                max = Math.max(max, currLength - 1);
            }
            deque.addFirst(currLength);
        }
        return max;
    }
}

 31.56 %
class Solution {
    public int lengthLongestPath(String input) {
        if (input == null) {
            return 0;
        }
        String[] dirs = input.split("\n");
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        for (String dir : dirs) {
            int level = dir.lastIndexOf("\t") + 1;
            while (stack.size() > level) {
                stack.removeFirst();
            }
            int len = (stack.isEmpty() ? 0 : stack.peekFirst()) + dir.length() - level + 1;
            stack.push(len);
            if (dir.contains(".")) {
                max = Math.max(max, len - 1);
            }
        }
        return max;
    }
}


看到以后完全懵逼，一点做过的印象都没有了
java String.length() treats "\t" as 1 character!

思路是如果是一个最长的path那么一定是一路走到底的，所以可以用一个array一路Update走过的各个level的length
一旦调回到某一个level，它之前的level Length依然有效，然后也会继续向更深的Level进行Update从而把之前的Length覆盖掉

-level是减掉path[i]里面相应个数的"\t"
+1是加 "\"
最后比max的时候"-1"是因为最后少一个"\"

二刷
44.77 %
class Solution {
    public int lengthLongestPath(String input) {
        if (input == null) return 0;
        String[] path = input.trim().split("\n");
        int[] levelLength = new int[path.length + 1];
        int maxLength = 0;
        int level = 0;
        for (int i = 0; i < path.length; i++) {
            // "-1" if not found
            level = path[i].lastIndexOf("\t") + 1;
            levelLength[level] = (level > 0 ? levelLength[level - 1] : 0) + path[i].length() - level + 1;
            if (path[i].contains(".")) maxLength = Math.max(maxLength, levelLength[level] - 1);
        }
        return maxLength;
    }
}


一刷

36.93 %
public class Solution {
    public int lengthLongestPath(String input) {
        if (input == null || input.length() == 0) return 0;
        String[] path = input.split("\n");
        //index -> level, value -> current length
        int[] stack = new int[path.length];
        int level;
        int maxLength = 0;
        for (String str : path) {
         
            level = str.lastIndexOf("\t") + 1;
            //System.out.println("level=" + level);
            //System.out.println("length=" + str.length());
            if (level == 0) {
                stack[level] = str.length();
            } else {
                stack[level] = stack[level - 1] + str.length() - level + 1;
            }
            //System.out.println(stack[level]);
            if (str.contains(".")) maxLength = Math.max(maxLength, stack[level]);
        }
        return maxLength;
    }
}