388 Longest Absolute File Path

388. Longest Absolute File Path

1. Question

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 directorydircontains an empty sub-directorysubdir1and a sub-directorysubdir2containing a filefile.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 directorydircontains two sub-directoriessubdir1andsubdir2.subdir1contains a filefile1.extand an empty second-level sub-directorysubsubdir1.subdir2contains a second-level sub-directorysubsubdir2containing a filefile2.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 is32(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, return0.

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)wherenis the size of the input string.

Notice thata/aa/aaa/file1.txtis not the longest file path, if there is another pathaaaaaaaaaaaaaaaaaaaaa/sth.png.

2. Implementation

(1) HashMap

思路: 我们将输入的input按照"\n"分成不同的行，然后通过得到最后一个"\t"的位置得知当前的line应该在哪个level，注意root directory是在level 1而不是level 0，比如"a/aa/aaa/file1.txt"这个例子中，"a"是在level 1, "aa"是在level 2.如果当前的line包含"."，说明这行有文件，我们到了file path的结尾，这时我们更新res。否则的话，将当前level + 1的从root directory到现在的level的长度存在map里

class Solution {
    public int lengthLongestPath(String input) {
        if (input == null || input.length() == 0) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;

        String[] lines = input.split("\n");

        for (String line : lines) {
            int level = line.lastIndexOf("\t") + 1;
            int len = line.length() - level;

            // We find the end of file path (a file), so update the max len
            if (line.contains(".")) {
                res = Math.max(res, map.getOrDefault(level, 0) + len);
            }
            else {
                // mpa.getOrDefault(level, 0) + len + 1 means get the len of last level plus the len of current level 
                // and plus 1 because of adding "/"
                map.put(level + 1, map.getOrDefault(level, 0) + len + 1);
            }
        }
        return res;
    }
}

3. Time & Space Complexity

HashMap: 时间复杂度O(n), 空间复杂度O(n)