38ms python code use stack

  • 0

    The basic idea is pretty same with the others. Use stack and keep track of the level of the file (the number of '\t' in each part) when loop over the list (which was split with '\n').

    Whenever the current level is higher than the previous level, append the current part (file or folder). If this is a file ('.' in it), update the max length.

    If the current level is not higher than the previous level, pop the current part (don't forget updating the levels) until it does.

    def lengthLongestPath(input):
        # use stack
        path, maxLen = [], 0
        pre_lvl = -1
        path = []
        for s in input.splitlines():
            cur_lvl = s.count('\t')  
            if cur_lvl > pre_lvl: # this is a new level
                path.append(s.lstrip('\t')) # this is another level of path
                pre_lvl = cur_lvl
            else: # pop the last part until current level bigger than pre level
                while cur_lvl <= pre_lvl:
                    pre_lvl -= 1
                pre_lvl = cur_lvl
            if '.' in s: # this is a file, update the maxLen here
                thisLen = len(''.join(path)) + len(path) - 1
                if thisLen > maxLen:
                    maxLen = thisLen
        return maxLen

Log in to reply

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