題目網址：https://leetcode.cn/problems/longest-absolute-file-path/

題意：假設有一個同時儲存檔案和目錄的 file system。下圖展示了 file system 的一個範例：

dir 作為根目錄中的唯一目錄, 其中 dir 包含兩個子目錄 subdir1 和 subdir2

  • subdir1 包含檔案 file1.ext 和子目錄 subsubdir1
  • subdir2 包含子目錄 subsubdir2, 該子目錄下包含檔案 file2.ext

文字格式如下所示（其中 ⟶ 表示 tab）：

上面的 file system 以 code 格式可表示為（其中 \n、\t 分別表示 換行、tab）

file system 中每個檔案、目錄都有一個唯一的絕對路徑, e.g. file2.ext 的絕對路徑是 dir/subdir2/subsubdir2/file2.ext

  • 每個目錄名由字母、數字、/ or 空格所組成
  • 每個檔案名遵循 name.extension 的格式, 其中 name 和 extension 由字母、數字和、/ or 空格所組成

給一 file system 的 code 格式 string input, 返回 file system 中指向檔案的最長絕對路徑之長度。若 file system 中沒有檔案, 則返回 0。

Solution：

想法：level 最大的 file 絕對路徑的長度不一定會是最長的 , 所以不能直接使用 Greedy。e.g. 下圖中, level 較大的 dir/abc/1.txt 長度比 dir/123456789.jpg 小

故分成以下步驟：

  • 先根據 \\n 拆出每個 file
  • 再根據 \\t 計算出當前 file 的 level
  • 將 file 中的 \\t 去掉, 並加入到 dir[level] 中
  • 加總 sum{dir[i] | 0 ≤ i ≤ level}, 最後再加上 level（因為每一個 level 都會在絕對路徑中產生一個 /）

e.g. input = dir\\n\\tsubdir1\\n\\tsubdir2\\n\\t\\tfile.ext

  • 首先, 會先拆出 dir、\\tsubdir1、\\tsubdir2、\\t\\tfile.ext 四個 file
  • 最一開始, dir 會是空的, 然後會隨著 file 的 level 增加而不斷 resize
  • 將每個 file 根據 level 加入到 dir 中, 若該 file 包含 . 則要計算長度
    • file dir 的 level = 0 ➔ dir[0] = dir
    • file \\tsubdir1 的 level = 1 ➔ dir[1] = subdir1
    • file \\tsubdir2 的 level = 1 ➔ dir[1] = subdir2 直接覆蓋掉原本的 dir[1]
      （直接覆蓋是沒問題的, 因為當某個 file.ext 被加入時, 其所有 parent dir 一定都在 dir 中, 因為其 parent dir 一定會先被拜訪, 並覆寫掉之前 file 的 dir 資訊）
    • file \\t\\tfile.ext 的 level = 2 ➔ dir[2] = file.ext
  • 因為 file.ext 為檔案, 故要加總當前 dir[0~level] 的長度
  • 此時加總了 dir、subdir2、file.ext 的長度, 但別忘了絕對路徑是 dir/subdir2/file.ext, 還要加上 / 的個數, 也就是 file.ext 的 level 才為答案
class Solution {
public:
    int lengthLongestPath(string input) {
        const int n = input.size();
        vector<string> files;

        // 根據 \\n 切割出 file
        for (int i = 0; i < n; ++i) {
            const int start = i;
            while (i < n && input[i] != '\\n') {
                ++i;
            }
            files.emplace_back(input.substr(start, i - start));
        }

        int res = 0;
        vector<string> dir;

        for (const auto& file : files) {
            int level = 0;

            // 根據 \\t 計算當前 file 的 level
            while (level < file.size() && file[level] == '\\t') {
                ++level;
            }

            // 若 dir 的 level ≤ 當前 file 的 level, 則重新 resize
            if (dir.size() <= level) {
                dir.resize(level + 1);
            }

            // 將去掉 \\t 的 file 放入 dir 中
            dir[level] = file.substr(level);

            // 若當前的 file 為檔案（包含 "."）, 則計算其絕對路徑的長度
            if (dir[level].find('.') != string::npos) {
                int len = 0;
                for (int i = 0; i <= level; ++i) {
                    len += dir[i].size();
                }
                len += level; // 加上 level, 因為每一個 level 都會在絕對路徑產生一個 "/"
                res = max(res, len);
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ for loop 遍歷 input
  • space：$O(n)$ ➔ files 紀錄每個 file 的名稱