题目要求
Suppose we abstract our file system by a string in the following manner:
The string “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext” represents:
dir
subdir1
subdir2
file.ext
The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.
The string “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext” represents:
dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2 contains a second-level sub-directory subsubdir2 containing a file file2.ext.
We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is “dir/subdir2/subsubdir2/file2.ext”, and its length is 32 (not including the double quotes).
Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return 0.
Note:
The name of a file contains at least a . and an extension.
The name of a directory or sub-directory will not contain a ..
Time complexity required: O(n) where n is the size of the input string.
Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.
要求从 String 字符串中找到最长的文件路径。这里要注意，要求的是文件路径，文件夹路径不予考虑。文件和文件夹的区别在于文件中一定包含.。
这里 \n 代表根目录平级，每多一个 \t 就多一层路径，这一层路径都是相对于当前的上层路径的。以 dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext 为例 dir 为第 0 层目录 \n\tsubdir1 代表 subdir1 是第一层目录，且其是当前父目录 dir 的子目录 \n\t\n\tsubdir2 代表 subdir2 为第一层目录，且其是当前父目录 dir 的子目录，此时的一级父目录从 subdir1 更新为 subdir2\n\t\tfile.ext 代表 tfile.ext 为二级目录，位于当前一级目录 subdir2 之下
思路和代码
综上分析，我们可以记录一个信息，即当前每一级的目录究竟是谁，每次只需要保留当前一级目录已有的路径长度即可。还是拿上面的例子 dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext：
遍历完 dir: 0 级目录长度为 3
遍历完 \n\tsubdir: 0 级目录长度为 3, 1 级目录长度为 11（dir/subdir1）
遍历完 \n\tsubdir2: 0 级目录长度为 3, 1 级目录长度为 11（dir/subdir2）
遍历完 \n\t\tfile.ext: 0 级目录长度为 3, 1 级目录长度为 11（dir/subdir2）, 2 级目录长度为 20
综上，最长的文件路径长为 20
代码如下：
public int lengthLongestPath(String input) {
if(input==null || input.isEmpty()) return 0;
// 记录当前每一级路径对应的路径长度
List<Integer> stack = new ArrayList<Integer>();
int left = 0, right = 0;
int max = 0;
int curDepth = 0;
// 当前遍历的是文件还是文件夹
boolean isFile = false;
while(right < input.length()) {
char c = input.charAt(right);
if(c == ‘\n’ || c == ‘\t’) {
// 如果是文件分割符的起点，则处理前面的字符串
if(right-1>=0 && input.charAt(right-1)!=’\n’ && input.charAt(right-1)!=’\t’) {
int length = right – left;
if(stack.isEmpty()) {
stack.add(length+1);
}else if(curDepth == 0){
stack.set(0, length+1);
}else{
int prev = stack.get(curDepth-1);
int now = prev + length + 1;
if(stack.size() <= curDepth) {
stack.add(now);
}else{
stack.set(curDepth, now);
}
}
if(isFile) {
max = Math.max(max, stack.get(curDepth)-1);
}
left = right;
isFile = false;
}
// 如果是文件分隔符的末尾，则处理文件分隔符，判断是几级路径
if(right+1<input.length() && input.charAt(right+1)!=’\n’ && input.charAt(right+1) !=’\t’){
curDepth = right – left;
left = right+1;
}
}else if(c == ‘.’) {
isFile = true;
}
right++;
}
// 处理最后的字符串
if(left != right && isFile) {
if(curDepth == 0) {
max = Math.max(max, right – left);
}else {
max = Math.max(max, stack.get(curDepth-1) + right – left);
}
}
return max;
}