C++ using stack, O(n), with explanation


  • 0
    L
    class Solution {
    public:
        int lengthLongestPath(string input) {
            if(input.empty()) return 0;
            stack<string> s;
            int res = 0;
            int i = 0;
            int level = 0;
    
            s.push("");//redundancy for root directory
            s.push("/");
        
            while(i < input.size()){
                int curLevel = 0;
                string temp = "";
                while((input[i] == '\n' || input[i] == '\t') && i < input.size()){
                    if(input[i] == '\t') curLevel++;
                    i++;
                }
                
                if(curLevel > level){//open child directory
                    level = curLevel;
                    temp = s.top();
                }
                else if(curLevel == level){//in same directory
                    s.pop();
                    temp = s.top();
                }
                else{//go back to parent directory
                    for(int i = 0; i <= level - curLevel; ++i) s.pop();//backtracing
                    level = curLevel;
                    temp = s.top();
                }
                
                string name = ""; 
                bool isFile = false;
                while(i < input.size() && input[i] != '\n'){
                    if(input[i] == '.') isFile = true;
                    name += input[i++];
                }
                temp += name;
                if(isFile && temp.size() > res) res = temp.size();//it is a file
                else{//it is a directory
                    temp += '/';
                }
                s.push(temp);
            }
            return res;
        }
    };
    

Log in to reply
 

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