9 lines 4ms Java solution


  • 110
    public int lengthLongestPath(String input) {
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(0); // "dummy" length
            int maxLen = 0;
            for(String s:input.split("\n")){
                int lev = s.lastIndexOf("\t")+1; // number of "\t"
                while(lev+1<stack.size()) stack.pop(); // find parent
                int len = stack.peek()+s.length()-lev+1; // remove "/t", add"/"
                stack.push(len);
                // check if it is file
                if(s.contains(".")) maxLen = Math.max(maxLen, len-1); 
            }
            return maxLen;
        }
    

    An even shorter and faster solution using array instead of stack:

    public int lengthLongestPath(String input) {
        String[] paths = input.split("\n");
        int[] stack = new int[paths.length+1];
        int maxLen = 0;
        for(String s:paths){
            int lev = s.lastIndexOf("\t")+1, curLen = stack[lev+1] = stack[lev]+s.length()-lev+1;
            if(s.contains(".")) maxLen = Math.max(maxLen, curLen-1);
        }
        return maxLen;
    }
    

  • 3

    Actually I'm assuming there is no "\t" in directory of file name. Otherwise using s.lastIndexOf("\t")+1 to find number of "\t"s will not be applicable.


  • 0
    I

    @sky-xu no need to push or store the len if it is a file.


  • 0
    I

    Hello, I am confused about how can you find the number of "\t" by s.lastIndexOf("\t")+1.


  • 3

    @sky-xu said in 9 lines 4ms Java solution:

    Actually I'm assuming there is no "\t" in directory of file name. Otherwise using s.lastIndexOf("\t")+1 to find number of "\t"s will not be applicable.

    @icezhou0784 As I mentioned, I'm assuming that "\t"will appear only before the directory or file name. For example, if s = "\t\t\tdirname", then s.lastIndexOf("\t") will be 2, the number of "\t" will be 3. If a diretory name does not contain"\t", then s.lastIndexOf("\t") will be -1, the number of "\t" will be 0.
    However, if "\t" is allowed within the directory or file name, then this way does not work.


  • 0
    I

    @sky-xu

    Thanks for your detailed explanation! I didn't count "\t" as a whole string, so the index of DP array messed up.


  • 39
    H

    Just pay attention that in String "\n", "\t", "\123" will all be count the length as one


  • 0
    Y

    @sky-xu In the second solution, can you explain why the length of stack is initialized as "input.lastIndexOf("\n)+3"?


  • 0

    @ysx0605hotmail.com I just realized that I made a mistake. I intended to initialize the array size with 1+number of lines. Thanks for pointing out!


  • 0
    Z
    This post is deleted!

  • 0
    M

    @hongyi5 Thx for pointing this out.


  • 9
    M

    Thanks for posting a neat and clear answer. I wrote a C++ version based on yours which could run in 0 ms.

    vector<string> split(string &s) {
        vector<string> ret;
        stringstream ss(s);
        string str;
        while (getline(ss, str)) {
            ret.push_back(str);
        }
        return ret;
    }
    int lengthLongestPath(string input) {
        vector<string> v = split(input);
        vector<int> level (100, 0);
        int maxLen = 0;
        for (string s: v) {
            int lv = s.find_last_of('\t') + 1;
            level[lv+1] = level[lv] + s.length() - lv + 1;
            if (s.find('.') != -1) maxLen = max(maxLen, level[lv+1] - 1);
        }
        return maxLen;
    }
    

  • 2

    @hongyi5 Thanks for clearing it up.
    I was confused that why "\t\tfile.ext".lastIndexOf("\t") and "&t&tfile.ext".lastIndexOf("&t") have different results.


  • 0
    L

    Hi, I am confused about how can your solution handles this test case "dir\n file.txt"?
    Thanks~


  • 0
    This post is deleted!

  • 0

    @liy46 that case should be included


  • 0
    B

    Hi what if you don't push 0 into stack at the beginning? I know len = stack.peek() need to be modified, but will there be other problems?


  • 0
    B

    Hi what will be the correct result for "a\n\tb\n\tc\n\t\te.ext\n\t\t\t\tf\n\t\t\t\tr.ext"?


  • 0
    B

    @xuehaohu Hi what will be the correct result for "a\n\tb\n\tc\n\t\te.ext\n\t\t\t\tf\n\t\t\t\tr.ext"?


  • 0
    B

    And if there are multiple space between \n and the name of the folder e.g "a\n b\t\t\tc.ext" how to handle it?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.