Explains the case of 4 spaces and tabs. Solve using stack and recursion


  • 0
    M

    Simply put, in this problem 4 spaces equals 1 tab. More importantly, the file system has the hierarchy that one file/directory can only be one tab or 4 spaces away from its parent directory. So the case "dir\n(8 spaces)file.txt" will has solution 16 "dir/(4 spaces)file.txt" instead of 12 "dir/file.txt"

    Stack solution:

    """

    int lengthLongestPath(string input) {
        stack<int> sk; //store cumulative length
        int pos=0, max_len=0;
        while(pos<input.length()) {
            int level = 0;
            if(input[pos]=='\n') {
                ++pos; // pass '\n'
                while(level<sk.size() && (input[pos]=='\t' || input[pos]==' ')) {
                    if(input[pos]=='\t') pos+=1;
                    else pos+=4;
                    ++level;
                }
            }
            
            while(sk.size() > level) // pop up stack so its size equals current level
                sk.pop();
            
            int len=0;
            bool isfile=false;
            while(pos<input.length() && input[pos]!='\n') {
                if(input[pos]=='.') 
                    isfile=true;
                ++pos;
                ++len;
            }
            
            int cum_len = sk.empty()? len:len+sk.top()+1;
            if(isfile) max_len = max(max_len,cum_len);
            else sk.push(cum_len);
        }
        return max_len;
    }
    

    """

    Recursion solution:

    """

    int lengthLongestPath(string input) {
        int maxlen=0, pos=0;
        while(pos<input.length()) {
            dfs(input,pos,0,0,maxlen);
            ++pos;
        }
        return maxlen;
    }
    
    
    void dfs(const string& s, int& pos, int level, int len, int& maxlen) {
        bool isfile = false;
        while(pos<s.length() && s[pos]!='\n') {
            if(s[pos]=='.') isfile=true;
            ++pos;
            ++len;
        }
        while(pos<s.length()) {
            int level2=0, pos2=pos;
            ++pos2;
            while(pos2<s.length() && (s[pos2]=='\t' || s[pos2]==' ')) {
                if(s[pos2]=='\t') pos2+=1; // 1 tab
                else pos2+=4; //4 spaces
                if(++level2 > level) break;
            }
            if(pos2<s.length() && level2>level) {
                pos=pos2;
                dfs(s,pos,level2,len+1,maxlen); //len+1 is for the sign '/' 
            }
            else {
                break;
            }
        }
        if(isfile) maxlen = max(maxlen,len);
    }
    

    """


Log in to reply
 

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