3ms, easy to understand c++ solution with word stack


  • 0
    E
    int lengthLongestPath(string input) {
            stack<string> wordStack;
            stack<int> levelStack;
            int maxLen = 0, currLen = 0;
            int i = 0, currLevel = 0;
            
            while(i < input.size()) {
                // Read the current word
                int ni = i;
                string currString="";
                bool isFile = false;
                while(ni < input.size() && input[ni] != '\n') {
                    currString+=input[ni];
                    if(input[ni] == '.') isFile = true;
                    ni++;
                }
                
                // Process the current word
                while(!levelStack.empty() && levelStack.top() >= currLevel) {
                    levelStack.pop();
                    currLen-=((wordStack.top()).size()+1);
                    wordStack.pop();
                }
                wordStack.push(currString);
                levelStack.push(currLevel);
                currLen+=(currString.length()+1);
                if(isFile) maxLen = max(maxLen, currLen);
                
                //Move on to the next word
                if(ni++ < input.size()) currLevel = 0; // if newline character is seen, reset the running level
                while(ni < input.size() && input[ni++] == '\t') currLevel++; // for each tab character, increment the running level
                i = ni; // update loop index i
            }
            return (maxLen > 0) ? maxLen-1 : 0;
        }
    

Log in to reply
 

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