Skip to content

388. Longest Absolute File Path 👎

  • Time: $O(n)$
  • Space: $O(n)$
 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
struct T {
  int depth;
  size_t length;
  T(int depth, size_t length) : depth(depth), length(length) {}
};

class Solution {
 public:
  int lengthLongestPath(string input) {
    size_t ans = 0;
    stack<T> stack{{{-1, 0}}};  // placeholder
    istringstream iss(input);

    for (string token; getline(iss, token, '\n');) {
      const int depth =
          count_if(begin(token), end(token), [](char c) { return c == '\t'; });
      token.erase(remove(begin(token), end(token), '\t'), end(token));
      while (depth <= stack.top().depth)
        stack.pop();
      if (isFile(token))
        ans = max(ans, stack.top().length + token.length());
      else  // directory + '/'
        stack.emplace(depth, stack.top().length + token.length() + 1);
    }

    return ans;
  }

 private:
  bool isFile(const string& token) {
    return token.find('.') != string::npos;
  }
};
 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
class T {
  public int depth;
  public int length;
  public T(int depth, int length) {
    this.depth = depth;
    this.length = length;
  }
}

class Solution {
  public int lengthLongestPath(String input) {
    int ans = 0;
    Deque<T> stack = new ArrayDeque<>();
    stack.push(new T(-1, 0));

    for (String token : input.split("\n")) {
      final int depth = getDepth(token);
      token = token.replace("\t", "");
      while (depth <= stack.peek().depth)
        stack.pop();
      if (token.contains(".")) // file
        ans = Math.max(ans, stack.peek().length + token.length());
      else // directory + '/'
        stack.push(new T(depth, stack.peek().length + token.length() + 1));
    }

    return ans;
  }

  private int getDepth(final String token) {
    return (int) token.chars().filter(c -> c == '\t').count();
  }
}
Back to top