Easy C++ solution using stack with explaination[AC]


  • 0

    Solution

    The problem is tricky as we have to traverse the directory tree with the help of '\t' and '\n' only. We will get different levels of string by dividing it by '\n'. Once, we do this, we can see that the last position of '\t' will give us the level of the tree. We will then proceed to find the length of the current string(which is the length minus the position of last '\t'). The tricky part is to get the length of the complete directory. We will maintain a stack which will store the length of the parent of a sub-directory. We will push the length of the parent into the stack. Interesting part to note is that for level 'l' the stack size will be smaller or equal to 'l'. If it is greater that means we have pushed some same level directories or sub-directories to it.
    For example, for level 1, the stack size should be equal to 1(only root should be present in the stack). If the stack size is 2 or more that means we have pushed some subdirectories or same level directories.

    To get the result we will check whether we reached the end of directory or not. If yes, we calculate the length

    Code

    class Solution {
    public:
        int lengthLongestPath(string input) {
            stringstream ss(input);
            stack<int> parentLen;
            string s;
            int res = 0;
            while(getline(ss,s , '\n'))
            {
                int level = s.rfind('\t')+1;
                int currentLength = s.length()-level;            
                while(parentLen.size() > level)
                    parentLen.pop();
                int lengthTillLvl = currentLength;
                if(!parentLen.empty())
                    lengthTillLvl+= parentLen.top();
                
                if(s.find('.')!=-1)
                    res = max(res, lengthTillLvl);
                else
                    parentLen.push(lengthTillLvl+1);
            }
            return res;
        }
    };
    

Log in to reply
 

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