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

  • 0

    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;
            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
                int level=pos;
                string cur="";//current dir or file name
                }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
                }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++){
                    res=max(res, temp+level);
                if(input.find('\t')==string::npos)break; //check if current dir is the last one
            return res;

Log in to reply

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