eighteen 、 The longest absolute path to the file

18.1、 Question design requirements

   Suppose you have a file system that stores files and directories at the same time . The following figure shows an example of a file system ：

   There will be dir As the only directory in the root directory .dir Contains two subdirectories subdir1 and subdir2 .subdir1 Include files file1.ext And subdirectories subsubdir1;subdir2 Include subdirectories subsubdir2, This subdirectory contains files 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 “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext” .‘\n’ and ‘\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 ‘/’ Connect . In the example above , Point to file2.ext Of Absolute path yes “dir/subdir2/subsubdir2/file2.ext” . Each directory name consists of the letters 、 Numbers and / Or spaces , Each file name follows name.extension The format of , among name and extension By letter 、 Numbers and / Or spaces .

   Give a string representing the file system in the above format input , Return to the file system Point to file Of Longest absolute path The length of . 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
 explain ： Only one file , The absolute path is  "dir/subdir2/file.ext" , The length of the path  20

Example 2：

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

Example 3：

 Input ：input = "a"
 Output ：0
 explain ： No files exist 

Example 4：

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

Tips ：

1 <= input.length <= 104
input  May contain lowercase or uppercase letters , A line break  '\n', A tab  '\t', One point  '.', A space  ' ', And number .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/longest-absolute-file-path

18.2、 Their thinking

   First use spilt(\n) Remove... From the string \n, Reuse \t Calculate the level of the string , Then use the backtracking of the stack to output the length of the directory contained in the string in the stack （ First judge whether the next level of the string is empty , If it is empty, you can directly calculate the file length name and return it . Not empty words , Determine whether it is a parent-child relationship , If you add the length directly ; If it's a file , Just calculate it directly ; If it's a catalog , Press it on the stack , then i++, Enter next cycle . If it is not a parent-child relationship , Stack pop operation , Until you step back to the last level of directory and keep it , Then go on to the next cycle .）, That's all I think .

18.3、 Algorithm

// First step ："\t" Representative hierarchy 
// The second step ：spilt(\n) Will be \n Get rid of , Output \t\t(......)str, Then we can according to \t To determine the level 
// The third step ： Stack backtracking (stack)
/* Step four ： * if(s.entry){ * * }else if( Superior and subordinate ){ * up.res(); * }else if(){ * pop; * } * */
class Solution {
    
    // Pack one Node
    class Node {
    
        //level Representative hierarchy 
        public int level;
        //sum Represents the length of the current directory 
        public int sum;

        public Node(int level,int sum){
    
            this.level = level;
            this.sum = sum;
        }
    }

    public int lengthLongestPath(String input){
    
        // Place the input string at  \n  Split when 
        String[] spilts = input.split("\n");
        // Use the stack to store elements 
        Deque<Node> stack = new ArrayDeque<>();
        // The result returned 
        int res = 0;
        for (int i = 0; i < spilts.length;) {
    
            // Judge different situations , First count how many tabs, That's how many \t, So that we can know which floor this is 
            int howManyTabs = countTab(spilts[i]);
            // If it is empty , Directly calculate the length of the file name 
            if (stack.isEmpty()){
    
                if (spilts[i].indexOf('.') != -1){
    
                    res = Math.max(res,spilts[i].length());
                }else {
    
                    Node newNode = new Node(howManyTabs,spilts[i].length() - howManyTabs);
                    stack.push(newNode);
                }
                i++;
            }else {
    
                // If it's not empty , First judge whether it is a parent-child relationship , If so, add the length directly ; If it's a file , Just calculate directly ; If it's a directory , take newNode Pressing stack , then i++.
                // If it is not a parent-child relationship , Stack pop operation , Until you go back to the last level of directory , Keep it .
                Node peek = stack.peek();
                // The relationship between superiors and subordinates 
                if (peek.level + 1 == howManyTabs){
    
                    Node newNode = new Node(howManyTabs,spilts[i].length() + peek.sum - howManyTabs + 1);

                    if (spilts[i].indexOf('.') != -1){
    
                        res = Math.max(res,newNode.sum);
                    }else {
    
                        stack.push(newNode);
                    }
                    i++;
                }else {
    
                    stack.pop();
                }
            }
        }
        return res;
    }

    // Calculation level 
    public int countTab(String s) {
    
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = 0; ; i++) {
    
            sb.append("\t");
            if (s.startsWith(sb.toString())){
    
                count++;
            }else {
    
                break;
            }
        }
        return count;
    }

}

Reference video ：B standing up Lord Guo wg