[LeetCode] Longest Absolute File Path

leetcode

This question is tricky – not just finding the deepest nested file, but the longest string.
For example, “dir/a/b/c/d/e/f/g/h.txt” is shorter than “dir/abcdefghijklmnopqrstuvwxy.txt”

There are also the weird test cases: sometimes there are meaningless empty spaces which you have to strip off first
Also, if there are directories but no “files” you have to return 0

I used a stack to keep track of the file path so far and the depth so far
If we see the current directory is less depth, we need to pop elements
Whenever we see a file (check if current directory is file by using str.find(‘.’) )
we compute the total length and compare to the longest length so far 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    """
    @param input: an abstract file system
    @return: return the length of the longest absolute path to file
    """
    def lengthLongestPath(self, input):
        if input == '': return 0

        paths = input.split('\n')

        if len(paths) == 1:
            if input.find('.') > 0:
                return len(paths[0])
            else: return 0
        stack = [paths.pop(0)]
        ans = 0
        depth = 0
        #import pdb; pdb.set_trace()
        while len(paths) > 0:
            cur_dir = paths.pop(0)
            cur_dir = cur_dir.split('\t')
            cur_depth = len(cur_dir) - 1
            cur = cur_dir[-1]
            cur = cur.replace(' ', '')

            if cur_depth <= depth:
                while cur_depth <= depth:
                    stack.pop()
                    depth -= 1

            if cur.find('.') > 0:
                # is file. find length and update
                l = len('/'.join(stack)) + len(cur) + 1
                if l > ans: ans = l
            else: # is dir, push and add depth
                stack.append(cur)
                depth += 1
        return ans