Stack Title: the longest absolute path of a file

subject

Title and provenance

title ： The longest absolute path to the file

Source ：388. The longest absolute path to the file

difficulty

7 level

Title Description

requirement

Suppose there is a file system to store files and directories . An example of a file system is shown in the following figure ：

There will be $\text{dir}$ As the only directory in the root directory .$\text{dir}$ Contains two subdirectories $\text{subdir1}$ and $\text{subdir2}$.$\text{subdir1}$ Include files $\text{file1.ext}$ And subdirectories $\text{subsubdir1}$;$\text{subdir2}$ Include subdirectories $\text{subsubdir2}$, This subdirectory contains files $\text{file2.ext}$.

In text format , As shown below （* Represents a tab ）：

dir
* subdir1
* * file1.ext
* * subsubdir1
* subdir2
* * subsubdir2
* * * file2.ext

In case of code representation , The above file system can be written as $\text{"dir}\backslash \text{n}\backslash \text{tsubdir1}\backslash \text{n}\backslash \text{tfile1.ext}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir1}\backslash \text{n}\backslash \text{tsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{t}\backslash \text{tfile2.ext"}$. among $\text{‘}\backslash \text{n’}$ and $\text{‘}\backslash \text{t’}$ Line breaks and tabs, respectively .

Each file and folder in the file system has a unique Absolute path , That is, you must open it to reach the file / Directory order of directory location , For all paths $\text{‘/’}$ Connect . In the example above , Point to $\text{file2.ext}$ The absolute path of $\text{"dir/subdir2/subsubdir2/file2.ext"}$. Each directory name consists of the letters 、 Numbers and / Or spaces , Each file name follows $\text{name.extension}$ The format of , Where the name and extension consist of the letters 、 Numbers and / Or spaces .

Give a string representing the file system in the above format $\text{input}$, Return to the file system The longest absolute path to a file The length of . If there are no files in the system , return $\text{0}$.

Example

Example 1：

Input ：$\text{input = "dir}\backslash \text{n}\backslash \text{tsubdir1}\backslash \text{n}\backslash \text{tsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{tfile.ext"}$
Output ：$\text{20}$
explain ： Only one file , The absolute path is $\text{"dir/subdir2/file.ext"}$, The length of the path $\text{20}$.

Example 2：

Input ：$\text{input = "dir}\backslash \text{n}\backslash \text{tsubdir1}\backslash \text{n}\backslash \text{t}\backslash \text{tfile1.ext}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir1}\backslash \text{n}\backslash \text{tsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{tsubsubdir2}\backslash \text{n}\backslash \text{t}\backslash \text{t}\backslash \text{tfile2.ext"}$
Output ：$\text{32}$
explain ： There are two files ：
$\text{"dir/subdir1/file1.ext"}$, The length of the path $\text{21}$.
$\text{"dir/subdir2/subsubdir2/file2.ext"}$, The length of the path $\text{32}$.
return $\text{32}$, Because this is the longest path .

Example 3：

Input ：$\text{input = "a"}$
Output ：$\text{0}$
explain ： No files exist .

Example 4：

Input ：$\text{input = "file1.txt}\backslash \text{nfile2.txt}\backslash \text{nlongfile.txt"}$
Output ：$\text{12}$
explain ： There is... In the root directory $\text{3}$ File .
Because the absolute path of anything in the root directory is the name itself , So the answer is $\text{"longfile.txt"}$, The path length is $\text{12}$.

Data range

• $\text{1}\le \text{input.length}\le {\text{10}}^{\text{4}}$
• $\text{input}$ May contain lowercase or uppercase English letters 、 A newline $\text{‘}\backslash \text{n’}$、 tabs $\text{‘}\backslash \text{t’}$、 spot $\text{‘.’}$、 Space $\text{‘ ’}$ And number

solution

Ideas and algorithms

Because each file and folder in the file system is separated by a newline , Therefore, the given input is separated into a string array according to the newline character , Each element in the string array is a file and folder , Just process each element in the string array .

For each file or folder , The number of tabs contained at the left end of the string is the level of the file or folder , The first $0$ The layer is the file or folder under the root directory . If a file or folder is not in the root directory , Then there must be a superior folder , The number of levels of the parent folder is the number of levels of the current file or folder minus $1$, And the position of the parent folder in the string array must be before the current file or folder .

For file systems with hierarchical relationships , Stack can be used to maintain the relative path length of each layer , At the same time, calculate the absolute path length of each layer . Because the stack stores the relative path length of each layer , Therefore, the location of each element in the stack reflects the level of the file or folder represented by this element , When there is $i$ Element time , The element at the top of the stack represents the $i-1$ The relative path length of the file or folder of the layer .

Traverse each element in the string array in turn , Maintain the elements in the stack and the absolute path length during traversal , Initially, the stack is empty , The absolute path length is $0$. The specific methods are as follows ：

1. For the current element in the string array , Calculate the number of tabs contained at the left end of the string , Get the level of the file or folder and the relative path length of the file or folder ;

2. If the number of elements in the stack is greater than the current level , The top of the stack element is removed from the stack , Until the number of elements in the stack is equal to the current level , At the same time, the stack elements are subtracted from the absolute path length ;

3. Stack the current relative path length , At the same time, add the current relative path length to the absolute path length ;

4. If the current element is a file , That is, the string contains a dot , Then the longest absolute path length of the file is updated according to the current absolute path length .

When calculating the relative path length of a file or folder , One detail to note is , Except for the files and folders under the root directory , The relative path of each of the remaining files and folders contains a $\text{‘/’}$, Therefore, when calculating the relative path length of files and folders , The relative path length of the file or folder under the root directory is the length of the string , The relative path length of a file or folder not under the root directory is the length of the string minus the number of tabs plus $1$（ Add $1$ Because it contains a $\text{‘/’}$）.

After the traversal , You can get the longest absolute path length of the file .

Code

class Solution {
    
    public int lengthLongestPath(String input) {
    
        String[] array = input.split("\n");
        int maxPathLength = 0;
        int pathLength = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int arrayLength = array.length;
        for (int i = 0; i < arrayLength; i++) {
    
            String str = array[i];
            int level = 0;
            while (str.charAt(level) == '\t') {
    
                level++;
            }
            int length = str.length() - level + (level == 0 ? 0 : 1);
            while (stack.size() > level) {
    
                pathLength -= stack.pop();
            }
            stack.push(length);
            pathLength += length;
            if (str.indexOf('.') >= 0) {
    
                maxPathLength = Math.max(maxPathLength, pathLength);
            }
        }
        return maxPathLength;
    }
}

Complexity analysis

• Time complexity ：$O(n)$, among $n$ Is string $\text{input}$ The length of . You need to traverse the string array once , The operation time of each character in the original input is $O(1)$.

• Spatial complexity ：$O(n)$, among $n$ Is string $\text{input}$ The length of . Space complexity mainly depends on string array and stack , The space complexity is $O(n)$.