JS force deduction daily question (2022 / 4 / 20) --388 The longest absolute path of the file

The longest absolute path to the file

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

/** * @param {string} input * @return {number} */
var lengthLongestPath = function(input) {
    
    //  Record the length of the depth  
    const map = new Map();
    const fileArray = input.split('\n');
    let res = 0;
    fileArray.forEach((line) => {
    
        let depth = count(line, '\t');

        map.set(depth, (map.get(depth - 1) ?? 0) + line.length - depth);

        if (line.includes('.')) {
    
            res = Math.max(res, map.get(depth) + depth)
        }
    })

    return res
};
function count(origin, target) {
    
    let times = 0;
    let index = origin.indexOf(target);

    while (index != -1) {
    
        times++;
        index = origin.indexOf(target, index + target.length);
    }
    return times;
}

This problem has become cv Transferred to the library , The problem is not difficult to understand , It is rare that the code is easy to implement , And the ability of programming ( This problem will be explained in detail after understanding )