题目描述
题目链接: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(包括
'/'
) 进栈中
代码如下:
#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