388. The longest absolute path to the file

Title Description ：

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 The absolute path of "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 , Where the name and extension consist of the letters 、 Numbers and / Or spaces .

requirement ：
Give a string representing the file system in the above format 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 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 = “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
Example 3：
Input ：input = “a”
Output ：0
explain ： No files exist

Be careful ：

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

Ideas ：

The file system is like a tree

Positive solution ：

func lengthLongestPath(input string) int {
    
	if input == "" || len(input) == 0 || !strings.Contains(input, ".") {
    
		return 0
	}
	//  The string is equivalent to... Of the tree dfs Depth-first search 
	// dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext
	// [dir \tsubdir1 \t\tfile1.ext \t\tsubsubdir1 \tsubdir2 \t\tsubsubdir2 \t\t\tfile2.ext]
	words := strings.Split(input, "\n")
	// pathLens[i] Deposit   The first i The path length of the last element of the hierarchy 
	pathLens := make([]int, len(words)+1)
	//  The lowest level is 1, In order to unify dp operation （ See the following circular body for details ）, take pathLens[0]=-1
	pathLens[0] = -1
	var ans int
	//  From left to right ,dp
	for _, word := range words {
    
		//  Hierarchical computing 
		// \t Number   Number of representative floors 
		//  Be careful ：
		// \n and \t All represent 1 position   Not two 
		// strings.LastIndex("\t\tsubdir1","\t")  The returned subscript is 1
		level := strings.LastIndex(word, string('\t')) + 1+1
		//  Calculate the length of the file name 
		// word :"\tsubdir1"
		// len(word) : 8
		// level:0
		// nameLen:9
		nameLen := len(word) - (level-1)
		// word The parent folder of must be currently level-1 The last of the hierarchy ,
		//  therefore pathLens[level-1] Is the path length of the parent folder 
		//  This word It must be the last one at this level ,
		//  Therefore, refresh is required pathLens[level],+1 Because we need to add one '\'
		pathLens[level] = pathLens[level-1] + 1 + nameLen
		//  If it's a file , Refresh with path length ans
		if strings.Contains(word, ".") {
    
			ans = int(math.Max(float64(ans), float64(pathLens[level])))
		}
	}
	return ans
}

Submit results ：