Leet Code OJ 388. Longest Absolute File Path [Difficulty: Medium]

2019-11-11 05:51:27

字体：大中小

来源：转载

供稿：网友

题目

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.

翻译

假定我们使用下面的方式来抽象文件系统：字符串”dir/n/tsubdir1/n/tsubdir2/n/t/tfile.ext” 代表:

dir subdir1 subdir2 file.ext

目录dir包含一个空的子文件夹subdir1和一个包含一个文件file.ext的子文件夹subdir2。字符串”dir/n/tsubdir1/n/t/tfile1.ext/n/t/tsubsubdir1/n/tsubdir2/n/t/tsubsubdir2/n/t/t/tfile2.ext” 代表:

dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext

找出这个文件系统中文件的最长路径，并返回它的路径长度。例如上述第二个例子的最长路径是”dir/subdir2/subsubdir2/file2.ext”,那么它的长度是32，包含“/”。提示: 1. 一个文件名应该至少包含一个”.”号和一个后缀名。 2. 文件夹则一定不包含”.”号。 3. 时间复杂度需要: O(n)。 4. 跟目录的层级无关。例如如果有一个路径是“aaaaaaaaaaaaaaaaaaaaa/sth.png”，那“a/aa/aaa/file1.txt”就不是最长的路径。

分析

首先，需要有个变量记录当前文件名的长度，和最大的长度maxLen。当切换到另外一个子目录的时候，为了能计算出当前长度，还需要保存它的父级目录的长度，所以我采用了栈结构来保存每一级目录的名称长度，并且使用depth来记录当前是第几个层级。其次，需要考虑’/n’和’/t’代表的含义。其中’/n’代表本次路径已经结束，可以开始计算结果并清空相关计数器。其中’/t’的个数代表当前是第几个层级。最后，考虑到题目只统计最长的文件路径，而不统计最长的文件夹路径，所以加个isFile来区分。

java版代码（时间复杂度O(n),空间复杂度O(n)）:

public class Solution { public int lengthLongestPath(String input) { input += "/n"; int count = 0; boolean isFile = false; int depth = 0; int maxLen = 0; Stack<Integer> stack = new Stack<>(); char[] charArr = input.toCharArray(); for (int i = 0; i < charArr.length; i++) { if (charArr[i] == '/n') { if (depth != 0) { count += stack.get(depth - 1) + 1; } while (stack.size() > depth) { stack.pop(); } stack.push(count); if (isFile) { if (count > maxLen) { maxLen = count; } } count = 0; depth = 0; isFile = false; } else if (charArr[i] == '/t') { depth++; } else { if (charArr[i] == '.') { isFile = true; } count++; } } return maxLen; }}

上一篇：深入了解AccessibilityService

下一篇：解决 Redis on Windows Setup Wizard ended prematurely