Python solution using stack


  • 0
    A

    main idea: use a stack to keep track of what depth you're at in the directory tree and also keep track of the length of path_string.

    class Solution(object):
        def lengthLongestPath(self, input):
            """
            :type input: str
            :rtype: int
            """
            dir_stack = [] #(total_dirs_len, dir_depth)
            max_len_path = 0
            for token in input.split('\n'):
                depth = 0
                while token.startswith('\t'):
                    depth += 1
                    token = token[1:]
                    
                while (len(dir_stack) > 0) and dir_stack[-1][1] >= depth:
                    dir_stack.pop()
                if '.' in token:
                    if(depth == 0):
                        max_len_path = max(len(token), max_len_path)
                    else:
                        max_len_path = max(dir_stack[-1][0] + len(token) + depth, max_len_path)
                else:
                    next_depth = len(token) + (dir_stack[-1][0] if depth > 0 else 0)
                    dir_stack.append((next_depth, depth))
            return max_len_path
    

Log in to reply
 

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