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

• 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);
}
``````

"""

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