requirements

Suppose you have a file system that stores both files and directories. The following figure shows an example of a file system:

Here, dir is the only directory in the root directory. Dir contains two subdirectories subdir1 and subdir2. Subdir1 contains the file file1.ext and subdirectory subsubdir1. Subdir2 contains subdirectory subsubdir2, which contains the file file2.ext.

In text format, it looks like this (⟶ represents tabs) :

Dir ⟶ subdir1 ⟶ ⟶ file1.ext ⟶ ⟶ subsubdir1 ⟶ subdir2 disk subsubdir2 file2.extCopy the code

In the case of a code representation, the file system above could be written as “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\ tsubdir2\n\t\ tfile2.ext”. ‘\n’ and ‘\t’ are newlines and tabs, respectively.

Each file and folder in the file system has a unique absolute path, which is the order of directories that must be opened to reach the location of the file/directory. All paths are connected with a ‘/’. In the example above, pointing to file2. Ext is the absolute path “dir/subdir2 / subsubdir2 / file2. Ext”. Each directory name is composed of letters, numbers, and/or Spaces, and each filename follows the format name.extension, where the name and extension are composed of letters, numbers, and/or Spaces.

Given an input string representing a file system in the format above, return the length of the longest absolute path in the file system to a file. If there are no files in the system, return 0.

Example 1:

Input: input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" Output: 20 Explanation: There is only one file, the absolute path is "dir/subdir2/file.ext", the path length is 20Copy the code

Example 2:

Input: input = "dir\n\tsubdir1\n\t\tfile1. Ext \n\t\ tsubdir1\n\ tsubdir2\n\t\ tsubdir2\n\t\ tfile2. Ext "output: 32 "Dir/subdir1 / file1. Ext", path length 21 "dir/subdir2 / subsubdir2 / file2. Ext", path length 32 return, because this is the longest pathCopy the code

Example 3:

Input: input = "a" Output: 0 Description: No file existsCopy the code

Example 4:

TXT \nfile2. TXT \nlongfile. TXT "Output: 12 Description: There are three files in the root directory. Since the absolute path to anything in the root directory is just the name itself, the answer is "longfile.txt" with a path length of 12Copy the code

Tip:

  • 1 <= input.length <= 104
  • Input may contain lowercase or uppercase letters, a newline character ‘\n’, a TAB character ‘\t’, a dot ‘.’, a space ‘, and a number.

The core code

class Solution:
    def lengthLongestPath(self, input: str) - >int:
        depth_dict = {0:0}
        max_dir_len = 0
        for line in input.split("\n"):
            depth = line.count("\t")
            name = line.lstrip("\t")
            cur_dir_len = len(name) + depth_dict[depth]
            if "." in name:
                max_dir_len = max(max_dir_len,cur_dir_len)
            else:
                depth_dict.update({depth + 1:cur_dir_len + 1})
        return max_dir_len
Copy the code

We use a dictionary to record the maximum depth and the maximum path length corresponding to the maximum depth. First separate all files or folders with \n, so that the number of “\t” in each element of the resulting list tells you the level of the file or folder. Set a dictionary that corresponds to the depth and length of the path, updating the current dictionary with each traversal. As for how to determine whether a path ends in a file, check whether there is a “. You can.