Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

388. Longest Absolute File Path

Time: $O(n)$

Space: $O(n)$

			


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;
  }
};




			


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();
  }
}