C++ 0ms using stack with comments


  • 0
    class Solution {
    private:
        tuple<bool, int, int> getNext(string& input, int& start) {   
            tuple<bool, int, int> ans(false, 0, 0);     // isFile, length, level
            
            while (input[start] == '\t') {
                get<2>(ans)++, start++;                 // count levels
            }
            
            while (start < input.length() && input[start] != '\n') {    // get string length and check if it's a file
                if (input[start] == '.') { get<0>(ans) = true; }
                get<1>(ans)++, start++;
            }
            start++;                                    // skip next '\n'
            return ans;
        }
        
    public:
        int lengthLongestPath(string input) {
            stack<int> st;
            int i = 0, len = 0, maxLen = 0;     // i: position in string, len: current total length in stack
            
            while (i < input.length()) {
                tuple<bool, int, int> cur = getNext(input, i);      // isFile, length, level
                
                while (st.size() > get<2>(cur)) {                   // get to the correct level
                    len -= st.top();
                    st.pop();
                }
                
                if (get<0>(cur)) {                                  // it's a file 
                    maxLen = max(maxLen, len + (int)get<1>(cur));   // drop the very first '/' before "dir", so didn't +1
                } else {                                            // it's a directory
                    len += get<1>(cur) + 1;                         
                    st.push(get<1>(cur) + 1);
                }
            }
            return maxLen; 
        }
    };
    

Log in to reply
 

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