LeetCode Longest Absolute File Path

· 132 words · 1 minute read
2017年6月
LeetCode

388.Longest Absolute File Path

Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"represents:

dir
    subdir1
    subdir2
        file.ext

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

方法

对于字符串解题，若要求时间复杂度为O(n)，除了设置两个指针，也要想到使用Stack

本题使用栈来存储深度(根据’\t’的个数)。 判断需要放在push之前

本题也有人使用str.lastIndexOf(String str)来确定\t的个数,该返回的为最后一个str的第一个字符，如果不出现，则返回-1。

public class Solution {
    public int lengthLongestPath(String input) {
        String[] s = input.split("\n");
        Stack<Integer> stack = new Stack<Integer>();
        int cur = 0; 
        int res = 0;
        for(String str : s){
            int level = count(str);
            //新的目录深度小于之前的，则从stack中pop()出
            while(stack.size() > level){
                cur = cur - stack.pop();
            }
            //加'/'
            cur = cur + str.replaceAll("\t","").length()+1;
            if(str.contains(".")){
                res = Math.max(res,cur-1);
            }
            stack.push(str.replaceAll("\t","").length()+1);
        }
        return res;
    }
    public int count(String str){
        String c = str.replaceAll("\t","");
        return str.length() - c.length();
    }
}
Share