388. Longest Absolute File Path

hashmap O(n) time O(lvl) space

class Solution {
public:
    int lengthLongestPath(string input) {
        unordered_map<int, int> m{{-1, 0}}; // 加一个-1方便运算
        int res = 0;
        istringstream iss(input);
        string s;
        while (getline(iss, s)) { // 直接读一行
            int lvl = s.find_first_not_of('\t'); // 数tab个数即为层数
            m[lvl] = s.length() - lvl + m[lvl - 1]; // 当前层的长度-tab个数+上一层的累加和 即为 当前层的累加和
            if (s.find('.') != string::npos) { // 如果是一个文件的话
                res = max(res, m[lvl] + lvl); // 切记需要加上slash个数才是真的长度！！！
            }
        }
        return res;
    }
};

stack O(n) time O(n) space

class Solution {
public:
    int lengthLongestPath(string input) {
        if (input.empty()) return 0;
        int res = 0;
        stack<string> s;
        input += '\n';
        int b = 0, e = input.find('\n'), lvl = 0, len = 0;
        for (; e != string::npos; e = input.find('\n', b)) {
            while (s.size() > lvl) {
                len -= s.top().length();
                s.pop();
            }
            s.push(input.substr(b, e - b + 1));
            len += s.top().length();
            if (s.top().find('.') != string::npos) {
                res = max(res, len - 1);
            }
            for (b = e + 1, lvl = 0; b < input.length() && input[b] == '\t'; ++b, ++lvl);
        }
        return res;
    }
};