LongestAbsoluteFilePath [source code]

public class LongestAbsoluteFilePath {
static
/******************************************************************************/
class Solution {
    public int lengthLongestPath(String input) {
        if (input.length () == 0)
            return 0;
        String[] tokens = input.split ("\\n");
        Inode[] inodes = new Inode[tokens.length];
        for (int i = 0; i < tokens.length; i++)
            inodes[i] = new Inode (tokens[i]);
        Deque<Inode> path = new ArrayDeque<> ();
        int sum = 0, max_path_len = 0;
        for (int i = 0; i < inodes.length; i++) {
            while (!path.isEmpty () && path.peek ().level >= inodes[i].level) {     // use while, not if
                sum -= path.pop ().length;
            }
            path.push (inodes[i]);
            sum += inodes[i].length;
            if (inodes[i].is_file)
                max_path_len = Math.max (max_path_len, sum + path.size () - 1);
        }
        return max_path_len;
    }

    static class Inode {
        int level, length;
        boolean is_file;

        Inode (String token) {
            level = 0;
            int i = 0;
            while (i < token.length()) {
                if (token.charAt (i) == '\t') {
                    level++;
                    i++;
                } else {
                    break;
                }
            }
            length = token.length () - i;
            is_file = token.contains (".");
        }

        public String toString () {
            return String.format ("[%d : %d%s]", level, length, is_file ? ".ext" : "");
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LongestAbsoluteFilePath.Solution tester = new LongestAbsoluteFilePath.Solution();
        String[] inputs = {
            "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext", "20",
            "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext", "32",
            "a.txt", "5",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            String input = inputs[2 * i];
            int ans = Integer.parseInt (inputs[2 * i + 1]), output = tester.lengthLongestPath (input);
            System.out.printf ("%s -> %s, expected: %d\n", 
                input, Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

有一个明显的tree结构, 但是题目的意思并不是很trivial; 当然可以考虑直接先build一个tree, 不过如果能直接做肯定是最好的;

整个文件系统就是一个PreOrder的tree, 然后最后让找的是一个类似maximum path sum (root to leaf)一样的东西; 下面就是考虑怎么从这个问题具体的描述当中抽象出来平常的tree问题的结构;

如果想要不做tree, 直接根据这个string就可以完成搜索, 那么脑子里面的过程应该是你在过给的这个FS的string, 然后你类似2sum的时候, 你这个时候应该维护什么信息, 能够保证足够告诉你你当前在tree里面的状态?

java> "\n".length ()  
java.lang.Integer res0 = 1  
java> "\\n".length ()  
java.lang.Integer res1 = 2

最近debug的时候喜欢打印iteration结束的时候的状态了, 反正这个也差不多; 另外, 每一个iteration的第一个print的开头打一个\n, 这样方便区分; 在其他地方打new line可能会有点麻烦, 因为可能会有各种premature exit;

这题的一个坑是, 虽然题目给的意思说是一个string, 但是他比如给的input里面, \n这样的东西, 实际上就是一个char, 也就是他给你input的时候, \没有escape; 难怪这题最后的downvote很高;

如果是escape了(我认为更加合理的设定), 那么对应的split记得要用: input.split ("\\\\n");

test3就比较恶心人, 所以这题其实并不是默认从dir开始; 这种实际面试的时候要问清楚面试官; 一般, 可以在最后提交之前问, 在一开始代码整体雏形还没有的时候, 可能想不到这么多, 先把逻辑想清楚比较重要;

最后超时才做出来, 主要是以前也没有过restore tree from preorder traversal的经历, 实际的代码就跟上面的一样了, 注意这个while的处理;

好像这个实际上比restore from preorder要简单一些, 因为这里是有明确的level标记的;

最后的速度是7ms (21%), 估计还是有更好的办法;

没有editorial;

https://leetcode.com/problems/longest-absolute-file-path/discuss/86615/9-lines-4ms-Java-solution

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;  
}

这个思路还是很清晰的, 相比于我的做法, 他想到了利用lastIndexOf来完成一个level的判断, 然后还想到了level全都是连续的, 所以当你知道当前的s的level的时候, 直接就很容易的可以知道自己的parent的level应该是多少: 把Stack pop到正好只剩下那么多就行了;

另外, 他Stack里面存的是path length, 而不是单独的一个token(去除level header之后的)的length; 这样就不用单独维护sum了;

这样他最开始的dummy也就是合理的, 最开始的path length实际上确实就是0;

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;  
}

深入理解了之前可以直接利用level连续性质来完成准确定位之后, 直接想到干脆就用一个array, level直接可以index进去;

Slightly longer version. But I think is way easier to understand.

• Only need -1 when it’s at root dir.
• Only add to stack if it isn’t an executable file.

public static int lengthLongestPath(String input) {  
    Stack<Integer> stack = new Stack<>();  
    stack.push(0);  // Layer 0, dummy head  
    int maxLen = 0;  
    for(String s : input.split("\\n")) {  
        int layer = s.lastIndexOf("\t") + 1;    // e.g. Layer 2 s: "     subsubdir1"  
        while(layer < stack.size() - 1)  
            stack.pop();  
        int length = stack.peek() + s.length() - layer + 1; // remove "\t..." add ""  
        if(layer == 0)  // dir has no "\t" in the front  
            length--;  
        if(s.contains("."))  
            maxLen = Math.max(maxLen, length);  
        else  
            stack.push(length);  
    }  
    return maxLen;  
}

第一条的优化比较trivial, 第二条还行, 不过算法逻辑并没有很大的改变;

@sky-xu said in 9 lines 4ms Java solution:
Actually I’m assuming there is no " " in directory of file name. Otherwise using s.lastIndexOf(" ")+1 to find number of " "s will not be applicable.
@icezhou0784 As I mentioned, I’m assuming that " "will appear only before the directory or file name. For example, if s = " dirname", then s.lastIndexOf(" ") will be 2, the number of " " will be 3. If a diretory name does not contain" ", then s.lastIndexOf(" ") will be -1, the number of " " will be 0.
However, if " " is allowed within the directory or file name, then this way does not work.

这个时候我这个手动的parse就有优势了; 我这个就算中间有空格或者tab, 都不影响;

To understand

while(level + 1 < stack.size()) stack.pop();

think an example that: we are somehow currently at " Abc.exe", whose level is 2. We only want to keep its ancestors in the stack, so that we can calculate the total length for this file path, so that is to say: we want our stack to store: dummy head, “dir” and " Parent". (actually store len instead of file name string). So the stack size we want is 3, so do stack.pop() till stack.size() == level +1.

这种代码就是要有一个例子在脑子里面;

https://leetcode.com/problems/longest-absolute-file-path/discuss/86619/Simple-Python-solution

The number of tabs is my depth and for each depth I store the current path length.

def lengthLongestPath(self, input):  
    maxlen = 0  
    pathlen = {0: 0}  
    for line in input.splitlines():  
        name = line.lstrip('\t')  
        depth = len(line) - len(name)  
        if '.' in name:  
            maxlen = max(maxlen, pathlen[depth] + len(name))  
        else:  
            pathlen[depth + 1] = pathlen[depth] + len(name) + 1  
    return maxlen

跟上一个解法后来给出的那个array做法是差不多的; 因为这题level直接给出了准确的定位能力, 所以并不需要依赖于Stack的动态变化的能力;

discussion基本即使这两种做法了; 注意array这种做法用HashMap来做也是一样的;

submission: 4(40):

public class Solution {  
    public int lengthLongestPath(String input) {  
        String[] inputs = input.split("\n");  
        int[] prevLength = new int[inputs.length];  
        int max = 0;  
        for (int i = 0; i < inputs.length; i++){  
            int lstIdx = inputs[i].lastIndexOf('\t');  
            int len = inputs[i].length() - lstIdx -1;  
            int totallen;   
            if (lstIdx == -1){  
               totallen = len;   
            }else{  
                totallen = len + prevLength[lstIdx] +1;  
            }   
            if (totallen > max && inputs[i].indexOf('.') != -1){  
                max = totallen;  
            }  
            prevLength[lstIdx+1] = totallen;  
        }  
        return max;  
    }  
}

好像还是差不多的, 这个逻辑写的实际上反而还混乱一点;

Problem Description

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

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir  
    subdir1  
        file1.ext  
        subsubdir1  
    subdir2  
        subsubdir2  
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is "dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.

Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

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.

Difficulty:Medium
Total Accepted:43.6K
Total Submissions:117K
Contributor:LeetCode
Companies
google