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

2019-11-11 06:27:50

字體：大中小

來源：轉載

供稿：網友

題目

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; }}

上一篇：bzoj 2718: [Violet 4] （floyed+匈牙利算法）

下一篇：每天寫n題：PAT-L1-001. Hello World