C++ solution using stack, 0ms


  • 0
    W

    There are only a few states during parsing:

    1. alphanumeric char, in these state, current length is counted.
    2. '\n', reset all the stats
    3. '\t', determine how many levels could be stored in stack.
    class Solution {
    public:
        int lengthLongestPath(string input) {
            input += '\n';
            stack<int> lenStk;
            int maxLen = 0;
            int stkDepth = 0;
            bool metChar = false;
            bool foundFile = false;
            int curLen = 0;
            for(int i = 0; i < input.length(); i++) {
                if(input[i] == '\t') {
                    stkDepth++;
                } else if(input[i] == '\n') {
                    curLen++;
                    metChar = false;
                    if(foundFile && curLen > maxLen)
                        maxLen = curLen;
                    if(curLen != 0)
                        lenStk.push(curLen);
                    foundFile = false;
                    curLen = 0;
                    stkDepth = 0;
                } else {
                    if(!metChar) {
                        metChar = true;
                        while(lenStk.size() > stkDepth) {
                            lenStk.pop();
                        }
                        if(lenStk.empty())
                            curLen = 0;
                        else
                            curLen = lenStk.top();
                    }
                    if(input[i] == '.')
                        foundFile = true;
                    curLen++;
                }
            }
            return max(0, maxLen-1);
        }
    };
    

Log in to reply
 

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