C++ O(n)


  • 0
    B

    having a parse function makes the code more readable, although it costs more time.

    class Solution {
    public:
        int lengthLongestPath(string input) {
            vector<string>parse = split(input);
            vector<int>pool;
            int ans = 0, cur = 0;
            for(auto e : parse)
            {
                int idx = 0, len = e.length();
                while(idx < len && e[idx] == '\t') idx++;
                while(pool.size() > idx)
                {
                    cur -= pool.back();
                    pool.pop_back();
                }
                if(e.find('.') != string::npos)
                {
                    ans = max(ans, len-idx+cur);
                }
                else
                {
                    pool.push_back(len-idx+1);
                    cur += pool.back();
                }
            }
            return ans;
        }
        
        vector<string> split(string input)
        {
            vector<string> ans;
            int idx = 0, len = input.length();
            while(idx < len && input[idx] != '\n')
            {
                idx++;
            }
            if(idx > 0) ans.push_back(input.substr(0,idx));
            if(idx < len)
            {
                auto next = split(input.substr(idx+1));
                for(auto e : next) ans.push_back(e);
            }
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.