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

我们一直在努力

apachecn/AiLearning

388 Longest Absolute File Path