C++ 0ms regular O(n) solution with explaination


  • 0
    M

    The main idea is: using a vector to store dir/file names while the index of the vector indicates the level/depth of the dir/file.

    (ie. for a path: "dir\n\tsubdir\n\tsubdir_second\n\t\tfile.txt", the sequence of the change of vector may look like:
    {"dir"} =>
    {"dir", "subdir"} =>
    {"dir", "subdir_second"} =>
    {"dir", "subdir_second", "file.txt"},
    the latest dir/file will overwrite the older one at the same index/level.)

    The function looks very huge, you're always welcomed to give a better and neater solution!

    int lengthLongestPath(string input) {
            //trim the tail, all the input after the last occurrence of file would not change the result
            int pos=input.find_last_of('.');
            if(pos==string::npos)return 0;    // if no file found, return 0
            int end=input.find_first_of('\n', pos);
            if(end!=string::npos) input=input.substr(0, end);  //trim the useless part
            
            //file exists, first get the root dir
            vector<string> dirs;
            pos=input.find_first_of('\n');
            dirs.push_back(input.substr(0, pos));  //consider the root dir to be level 0
            input=input.substr(pos+1); //trim the root dir
            
            int res=0; 
            pos=input.find_first_not_of('\t'); // the pos value means how many '\t' we have passed, so in file system also means the current level
    
            while(pos!=string::npos){
                int level=pos;
                input=input.substr(pos);
                
                string cur="";//current dir or file name
                end=input.find_first_of('\n');
                if(end!=string::npos){
                    cur=input.substr(0,end);
                    input=input.substr(end+1);
                }else cur=input;
                
                if(level==dirs.size()){ //if current dir or file is deepest level we haven't reached, add to the back of the vector
                    dirs.push_back(cur);
                }else dirs[level]=cur;  //if we have reached the same level, overwrite that level's name
                
                if(cur.find('.')!=string::npos){ //if current is a file, count the length of path
                    int temp=0;
                    for(int i=0;i<=level;i++){
                        temp+=dirs[i].length();
                    }
                    res=max(res, temp+level);
                }
                
                if(input.find('\t')==string::npos)break; //check if current dir is the last one
                
                pos=input.find_first_not_of('\t');
            }
            return res;
        }

Log in to reply
 

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