返回

[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(包括 '/') 进栈中

代码如下:

#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

Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy