0%

[Leetcode]388. Longest Absolute File Path(C++)

题目描述

题目链接:388. Longest Absolute File Path

题目描述比较复杂,具体见官网。基本上题目要求给定一个由字符串定义的文件目录树,从中提取出最长的文件路径(不包括文件夹)。其中字符串包括:

  • \n:换行,本身不代表什么含义,表示当前目录名/文件名的结尾
  • \t:表示文件/文件夹层级,例如,没有 \t 表示该文件(夹)是在最高一级目录,一个 \t 则表示其在下一层级,以此类推
  • 字母以及 .:组成文件夹名,如果包含 . 则为文件名(后缀一定存在)

例子

例子 1

Input: input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
Output: 20
Explanation: We have only one file, and the absolute path is “dir/subdir2/file.ext” of length 20.

例子 2

Input: input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.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.

例子 3

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

Constraints

  • 1 <= input.length <= 10^4
  • input may contain lowercase or uppercase English letters, a new line character ‘\n’, a tab character ‘\t’, a dot ‘.’, a space ‘ ‘, and digits.

解题思路

通过栈来管理不同层级的目录,遍历字符串:

  • 遇到 \n,表示当前文件名结束,继续遍历获得的下个目录/文件的层级:
    • \t 通过 Tab 的个数判断当前文件的层级,如果 Tab 个数小于 stack 中元素个数,则应该出栈直至栈中的元素个数等于当前层级
  • 然后获取文件名:
    • 如果是文件名,则将栈中元素相加获取目录长度+文件名长度即为当前文件长度
    • 如果是文件夹,则将文件夹名长度 + 1(包括 '/') 进栈中

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stack>
#include <string>

class Solution {
public:
int lengthLongestPath(std::string input) {
int max_length = 0;
int curr_length = 0;

int idx = 0;

std::stack<int> levels;

while (idx < input.length()) {
// case of newline
if (idx < input.length() && input[idx] == '\n') {
idx++;

// tabs must come after newline
int num_tab = 0;
while (idx < input.length() && input[idx] == '\t') {
num_tab++;
idx++;
}
while (levels.size() > num_tab) {
curr_length -= levels.top();
levels.pop();
}
}

int prev_idx = idx;
bool is_file = false;
while (idx < input.length() && input[idx] != '\n' &&
input[idx] != '\t') {
if (input[idx] == '.') is_file = true;
idx++;
}
// case of file
if (is_file) {
max_length =
std::max(curr_length + (idx - prev_idx), max_length);

} else { // case of dir
levels.push(idx - prev_idx + 1);
curr_length += idx - prev_idx + 1;
}
}

return max_length;
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 388.LongestAbsoluteFilePath.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions