388.Longest Absolute File Path

Tags: [stack]

Com: {g}

Link: https://leetcode.com/problems/longest-absolute-file-path/?tab=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 dircontains 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.

Better Understanding Solution: Stack

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        if not input:
            return 0

        partials = [x for x in input.split('\n') if x and x.strip()]
        max_len = 0
        curr_len = 0
        stack = []
        for i in xrange(len(partials)):
            curr_partial = partials[i]
            curr_level = curr_partial.count('\t')
            curr_partial = curr_partial[curr_level:]

            if stack and stack[-1][1] >= curr_level:
                top = stack.pop()
                if top[0].find('.') >= 0:
                    # the reason here plus the len(stack), 
                    # because there are '/' in the middle each two sub dir and file.
                    max_len = max(max_len, curr_len + len(stack))
                curr_len -= len(top[0])

                while stack and stack[-1][1] >= curr_level:
                    top = stack.pop()
                    curr_len -= len(top[0])

            stack.append((curr_partial, curr_level))
            curr_len += len(curr_partial)

        if stack and stack[-1][0].find('.') >= 0:
            top = stack.pop()
            max_len = max(max_len, curr_len + len(stack))

        return max_len

Revelation:

• Do not forget to check whether there exists a file path in the stack after the main loop.

Solution: stack

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        if not input:
            return 0

        level = 0
        segments = []
        buff = []
        index = 0
        while index < len(input):
            curr = input[index]
            if curr == '\n':
                if buff:
                    segment = ''.join(buff)
                    segments.append((segment, level))
                    buff = []

                tab_index = index + 1
                while tab_index < len(input) and input[tab_index] == '\t':
                    tab_index += 1

                num_of_tabs = tab_index - (index + 1)
                level = num_of_tabs
                index = tab_index
            else:
                buff.append(curr)
                index += 1

        if buff:
            segment = ''.join(buff)
            segments.append((segment, level))

        stack = []
        index = 0
        path_len = 0
        max_len = 0

        while index < len(segments):
            segment = segments[index]
            if not stack or segment[1] > stack[-1][1]:
                stack.append(segment)
                path_len += len(segment[0])
                index += 1
            else:
                # segment's level == current level
                if self.is_filename(stack[-1][0]):
                    max_len = max(max_len, path_len + len(stack) - 1)

                removed_segment = stack.pop()
                path_len -= len(removed_segment[0])

        if stack and self.is_filename(stack[-1][0]):
            max_len = max(max_len, path_len + len(stack) - 1)

        return max_len

    def is_filename(self, s):
        return s and 0 <= s.find('.') < len(s) - 1

Note:

• Time complexity = O(n), n is the length of the given input.
• In Python, string has 'find()' and 'index()' functions, the input of these two functions are substring. Given the substring, if substring exists in the main string, these two functions will return the index of the first char of substring in main string. The difference between these two functions are that if the given substring does not exist in the main string, 'find()' will return -1, and 'index()' will raise an exception (ValueError).
• In Python, array only has 'index()' function, to find the element's index in the array. If the given element does not exist in the main array, the 'index()' function will raise and exception (ValueError).