[LeetCode] 388. Longest Absolute File Path

Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:

Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext.

In text form, it looks like this (with ⟶ representing the tab character):

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

If we were to write this representation in code, it will look like this: "dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext". Note that the ' ' and ' ' are the new-line and tab characters.

Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by '/'s. Using the above example, the absolute path to file2.ext is "dir/subdir2/subsubdir2/file2.ext". Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.

Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Example 1:

Input: input = "dir
	subdir1
	subdir2
		file.ext"
Output: 20
Explanation: We have only one file, and the absolute path is "dir/subdir2/file.ext" of length 20.

Example 2:

Input: input = "dir
	subdir1
		file1.ext
		subsubdir1
	subdir2
		subsubdir2
			file2.ext"
Output: 32
Explanation: We have two files:
"dir/subdir1/file1.ext" of length 21
"dir/subdir2/subsubdir2/file2.ext" of length 32.
We return 32 since it is the longest absolute path to a file.

Example 3:

Input: input = "a"
Output: 0
Explanation: We do not have any files, just a single directory named "a".

Example 4:

Input: input = "file1.txt
file2.txt
longfile.txt"
Output: 12
Explanation: There are 3 files at the root directory.
Since the absolute path for anything at the root directory is just the name itself, the answer is "longfile.txt" with length 12.

Constraints:

• 1 <= input.length <= 104
• input may contain lowercase or uppercase English letters, a new line character ' ', a tab character ' ', a dot '.', a space ' ', and digits.

文件的最长绝对路径。

这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。subdir1 包含文件 file1.ext 和子目录 subsubdir1；subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。

在文本格式中，如下所示(⟶表示制表符)：

dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext
如果是代码表示，上面的文件系统可以写为 "dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext" 。' ' 和 ' ' 分别是换行符和制表符。

文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。上面例子中，指向 file2.ext 的绝对路径是 "dir/subdir2/subsubdir2/file2.ext" 。每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，其中名称和扩展名由字母、数字和/或空格组成。

给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向文件的最长绝对路径 的长度。 如果系统中没有文件，返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-absolute-file-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道字符串的题。题意不难懂，但是不容易做对。这里我提供一个 stack 的思路。stack 里面存的是每一层级目录的长度，stack 的深度表示到底有几层子目录。

题目说了 和 分别代表换行符和制表符，其中换行符表示的意思是进入下一层级的目录；制表符也是起辅助作用的，原则上每遇到一个换行符，后面紧接着就会跟若干个制表符，而且制表符的出现次数表示目录的层数。

比如题目中给的这个例子，遇到 dir 换行 ，换行的同时有 说明进入dir的下一级目录，所以图中的 subdir1 和 subdir2 是同级的。对于 subdir1 而言，他下面跟着两个换行符 ，说明他的下面还跟着两个子目录。这两个子目录各自出现两个制表符 说明这是之于 subdir1 而言再深一层的目录。

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

通过上面这个例子，我们发现其实我们可以把 input 先按照换行符分割开来。分割完毕之后，我们通过判断制表符的个数来判断到底当前这一行上的路径是上一行的子目录还是同级目录。我们跑一下example 2，input = "dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext"。按照 分割开来之后，我们得到如下，注意有缩进是因为 的关系。

dir
　　subdir1
　　　　file1.ext
　　　　subsubdir1
　　subdir2
　　　　subsubdir2
　　　　　　file2.ext

由于一开始的时候 stack 为空所以可以直接将 dir 的长度 3 放入 stack；再来碰到 subdir1 的时候，这时候我们要找最后一个 的位置 - 也就是算这一个子目录到底有多少个 ，以发现这个子目录的深度是多少。知道这个 level 之后，如果 level + 1 小于当前 stack 的深度，说明我们现在遍历的这一行是一个深度较小的目录，就可以从 stack 往外弹出元素了。

对于当前这一行目录的字符长度的计算，参见代码注释。最后注意如果在当前这一段里面遇到了点，说明已经到达文件名了，就可以结算长度了。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int lengthLongestPath(String input) {
 3         Stack<Integer> stack = new Stack<>();
 4         stack.push(0);
 5         int res = 0;
 6         String[] paths = input.split("
");
 7         for (String s : paths) {
 8             System.out.println(s);
 9             // 找到最后一个"	"的位置，注意找的时候，是会跳过的index的
10             int level = s.lastIndexOf("	") + 1;
11             System.out.println(level);
12             while (level + 1 < stack.size()) {
13                 stack.pop();
14             }
15             // 减level是因为需要减去字母t的长度
16             // + 1是因为需要带一个backslash的长度
17             int len = stack.peek() + (s.length() - level + 1);
18             stack.push(len);
19             if (s.contains(".")) {
20                 res = Math.max(res, len - 1);
21             }
22         }
23         return res;
24     }
25 }

LeetCode 题目总结