Skip to content

388 Longest Absolute File Path

388. Longest Absolute File Path

题目: https://leetcode.com/problems/longest-absolute-file-path/

难度:

Medium

思路

我们首先观察到每个文件夹或者是文件前面都会有一个'\n', 还有对应其层数个数的'\t'. - 所以首先根据'\n'分行,然后算出该文件/文件夹的层数depth - 如果是文件,我们需要更新maxlen - 如果是文件夹,我们需要更新该depth下的pathlen

程序变量解释

  • maxlen 代表目前最大子串的长度
  • pathlen 每一个depth下对应的path长度

特别需要注意的是,'\t'的长度是1

有的人仍然会有疑问,每次碰到文件夹都直接更新pathlen会不会导致本来长的反而变得短了,但是我们可以看到字符串的排版格式,每层path都是严格有自己的分级的, 因此不会出现这样的问题。 例如: - 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

其最大长度是32, "dir/subdir2/subsubdir2/file2.ext"

  • 如果变成"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir20\n\t\tsubsubdir2\n\t\t\tfile2.ext"
dir
    subdir1
        file1.ext
        subsubdir1
    subdir20
        subsubdir2
            file2.ext

最大长度就是33, "dir/subdir2/subsubdir20/file2.ext"

  • 如果变成 "dir\n\tsubdir1000000000000\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
dir
    subdir10000000000000
        file1.ext
        subsubdir1
    subdir20
        subsubdir2
            file2.ext

最大长度就是34,"dir/subdir10000000000000/file1.ext"

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        maxlen = 0
        pathlen = {0 : 0}
        for line in input.splitlines():
            name = line.lstrip('\t')
            depth = len(line) - len(name)        # 前面有几个'\t', depth就是几
            if '.' in name:
                maxlen = max(maxlen, pathlen[depth] + len(name))
            else:
                pathlen[depth+1] = pathlen[depth] + len(name) + 1    #加1是为了加上一个path分隔符'/'的长度
        return maxlen


回到顶部