388.文件的最长绝对路径

链接：388.文件的最长绝对路径
难度：Medium
标签：栈、深度优先搜索、字符串
简介：给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向 文件 的 最长绝对路径 的长度 。 如果系统中没有文件，返回 0。

题解 1 - typescript

• 编辑时间：2022-03-24
• 执行用时：68ms
• 内存消耗：42.4MB
• 编程语言：typescript
• 解法介绍：遍历，栈存储父级。

class FNode {
  parent: FNode | null = null;
  constructor(public name: string, public level: number) {}
  path() {
    let res = this.name;
    let parent = this.parent;
    while (parent) {
      res = parent.name + '/' + res;
      parent = parent.parent;
    }
    return res;
  }
  isFile() {
    return this.name.includes('.');
  }
}
function format(str: string): [number, string] {
  let level = 0;
  while (str[level] == '\t') level++;
  return [level, str.substr(level)];
}
function lengthLongestPath(input: string): number {
  const stack: FNode[] = [];
  let ans = '';
  for (const item of input.split('\n')) {
    const [level, str] = format(item);
    const node = new FNode(str, level);
    while (stack.length && stack[stack.length - 1].level >= level) stack.pop();
    if (stack.length) {
      const parent = stack[stack.length - 1];
      node.parent = parent;
    }
    stack.push(node);
    if (node.isFile()) {
      const path = node.path();
      ans = ans.length < path.length ? path : ans;
    }
  }
  return ans.length;
}

题解 2 - cpp

• 编辑时间：2022-04-20
• 内存消耗：6.4MB
• 编程语言：cpp
• 解法介绍：栈。

class Solution {
   public:
    int lengthLongestPath(string input) {
        vector<string> s;
        istringstream iss(input);
        string tmp;
        int ans = 0;
        while (getline(iss, tmp, '
')) {
            int idx = 0;
            while (idx < tmp.size() && tmp[idx] == '	') idx++;
            while (s.size() && s.size() > idx) s.pop_back();
            string next = tmp.substr(idx, tmp.size() - idx);
            s.push_back(next);
            if (next.rfind(".") < next.size()) ans = max(ans, format(s));
        }
        return ans;
    }
    int format(vector<string> &s) {
        int res = s.size() - 1;
        for (auto &str : s) res += str.size();
        return res;
    }
};