## Monday, August 22, 2016

### LeetCode 388 - Longest Absolute File Path

Suppose we abstract our file system by a string in the following manner:
The string `"dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"` represents:
```dir
subdir1
subdir2
file.ext
```
The directory `dir` contains an empty sub-directory `subdir1` and a sub-directory `subdir2` containing a file `file.ext`.
The string `"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"` represents:
```dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext
```
The directory `dir` contains two sub-directories `subdir1` and `subdir2``subdir1` contains a file `file1.ext` and an empty second-level sub-directory `subsubdir1``subdir2`contains a second-level sub-directory `subsubdir2` containing a file `file2.ext`.
We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is`"dir/subdir2/subsubdir2/file2.ext"`, and its length is `32` (not including the double quotes).
Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return`0`.
Note:
• The name of a file contains at least a `.` and an extension.
• The name of a directory or sub-directory will not contain a `.`.
Time complexity required: `O(n)` where `n` is the size of the input string.

Notice that `a/aa/aaa/file1.txt` is not the longest file path, if there is another path `aaaaaaaaaaaaaaaaaaaaa/sth.png`.

https://discuss.leetcode.com/topic/55247/9-lines-4ms-java-solution
``````public int lengthLongestPath(String input) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0); // "dummy" length
int maxLen = 0;
for(String s:input.split("\n")){
int lev = s.lastIndexOf("\t")+1; // number of "\t"
while(lev+1<stack.size()) stack.pop(); // find parent
int len = stack.peek()+s.length()-lev+1; // remove "/t", add"/"
stack.push(len);
// check if it is file
if(s.contains(".")) maxLen = Math.max(maxLen, len-1);
}
return maxLen;
}
``````
An even shorter and faster solution using array instead of stack:
``````public int lengthLongestPath(String input) {
String[] paths = input.split("\n");
int[] stack = new int[paths.length+1];
int maxLen = 0;
for(String s:paths){
int lev = s.lastIndexOf("\t")+1, curLen = stack[lev+1] = stack[lev]+s.length()-lev+1;
if(s.contains(".")) maxLen = Math.max(maxLen, curLen-1);
}
return maxLen;
}``````
https://discuss.leetcode.com/topic/55561/two-different-solutions-in-java-using-stack-and-hashmap
``````    public int lengthLongestPath(String input) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
int result = 0;
for (String s : input.split("\n")) {
int level = s.lastIndexOf("\t") + 1;
while (stack.size() != level) {
stack.pop();
}
int len = s.length() - level; // s.substring(level).length();
if (stack.isEmpty()) {
stack.push(len);
} else {
stack.push(stack.peek() + len + 1);
}
if (s.contains(".")) {
result = Math.max(result, stack.peek());
}
}
return result;
}``````
https://discuss.leetcode.com/topic/55088/java-o-n-solution-using-stack
The depth of the directory/file is calculated by counting how many "\t"s are there.
The time complexity is O(n) because each substring in the input string only goes into the stack once, and pops out from the stack once.
``````public class Solution {
public int lengthLongestPath(String input) {
String[] tokens = input.split("\n");
int result = 0;
int curLen = 0;
Stack<Integer> stack = new Stack<>();

for (String s : tokens) {
int level = countLevel(s);

// if current directory/file depth is lower that the top directory/file on the stack, pop from stack
while (stack.size() > level) {
curLen -= stack.pop();
}

// +1 here because a "/" needs to be counted following each diretory
int len = s.replaceAll("\t", "").length() + 1;
curLen += len;

// if s contains ".", we have found a file!
if (s.contains(".")) {
result = curLen - 1 > result ? curLen - 1 : result;
}
}
return result;
}

private int countLevel(String s) {
String cur = s.replaceAll("\t", "");
return s.length() - cur.length();
}
}``````
http://blog.csdn.net/qq508618087/article/details/52296490

`    ``public` `int` `lengthLongestPath(String s) {`
`        ``if` `(s == ``null` `|| s.length() == ``0``) {`
`            ``return` `0``;`
`        ``}`
`        ``String[] files = s.split(``"\n"``);`
`        ``int` `maxLen = ``0``;`
`        ``int` `pathLen = ``0``;`
`        ``Stack<Integer> dirLen = ``new` `Stack<>();`
`        ``for` `(``int` `i = ``0``; i < files.length; i++) {`
`            ``String curLine = files[i];`
`            ``int` `curLvl = findLvl(curLine);`
`            ``int` `lvDiff = dirLen.size() - curLvl;`
`            ``while` `(lvDiff > ``0``) {`
`                ``pathLen -= dirLen.pop();`
`                ``lvDiff -= ``1``;`
`            ``}`
`            ``int` `dotPos = curLine.indexOf(``'.'``);`
`            ``if` `(dotPos > -``1``) {`
`                ``maxLen = Math.max(maxLen, pathLen + curLine.length() - curLvl);`
`            ``} ``else` `{`
`                ``pathLen += curLine.length() - curLvl + ``1``;`
`                ``dirLen.push(curLine.length() - curLvl + ``1``);`
`            ``}`
`        ``}`
`        ``return` `maxLen;`
`    ``}`
`    ``private` `int` `findLvl(String s) {`
`        ``int` `count = ``0``;`
`        ``while` `(s.charAt(count) == ``'\t'``) {`
`            ``count += ``1``;`
`        ``}`
`        ``return` `count;`
`    ``}`
http://ninefu.github.io/blog/388-Longest-Absolute-File-Path/
http://codechen.blogspot.com/2016/08/leetcode388-longest-absolute-file-path.html
```    public int lengthLongestPath(String input) {
String[] lines = input.split("\n");
Stack<Integer> path = new Stack<>();
path.push(0);
int max = 0;

for (String line : lines) {
int tabIndex = line.lastIndexOf("\t") + 1;
while (path.size() - 1 > tabIndex) {
path.pop();
}
int length = path.peek() + 1 + line.length() - tabIndex;
path.push(length);
if (line.indexOf(".") != -1)
max = Math.max(max, length - 1);
}

return max;
}```
https://discuss.leetcode.com/topic/55129/a-simple-4ms-java-solution-with-explanation
1. use stack to maintain each layer's length by far
2. add up chars between '\n\t' to get file or direction's length (use '.' to distinguish them)
3. you either output a candidate pathLen if you got a file, or refresh your stack with the direction
4. to prepare for the next round, you have to count what's next file/direction's depth
``````    public int lengthLongestPath(String input) {

int max = 0, len = input.length(), idx = 0, pathLen = 0, curDepth = 0;
Stack<Integer> stk = new Stack<>();  //store diretion length in order, Notice stk.size is associate with curDepth
while(idx < len){
//first modify pathLen by popping out diretion_len that has greater depth
while(stk.size() > curDepth) pathLen -= stk.pop();

int curLen = 0; curDepth = 0;
boolean isFile = false;
//find the next dir or file length, check if it is a File
for(;idx < len && input.charAt(idx)!='\n';idx++, curLen++)
if(input.charAt(idx)=='.') isFile = true;

if(isFile) max = Math.max(max, curLen+pathLen); // isFile, then output cur total pathLen
else pathLen += stk.push(curLen+1);  // else, add it to stack & refresh pathLen

idx++; // idx now points to the char next to '\n'
for(;idx < len && input.charAt(idx)=='\t'; idx++) curDepth++; // find curDepth for the next round
}
return max;

}``````

https://discuss.leetcode.com/topic/55088/java-o-n-solution-using-stack
The depth of the directory/file is calculated by counting how many "\t"s are there.
The time complexity is O(n) because each substring in the input string only goes into the stack once, and pops out from the stack once.
``````    public int lengthLongestPath(String input) {
String[] tokens = input.split("\n");
int result = 0;
int curLen = 0;
Stack<Integer> stack = new Stack<>();

for (String s : tokens) {
int level = countLevel(s);

// if current directory/file depth is lower that the top directory/file on the stack, pop from stack
while (stack.size() > level) {
curLen -= stack.pop();
}

// +1 here because a "/" needs to be counted following each diretory
int len = s.replaceAll("\t", "").length() + 1;
curLen += len;

// if s contains ".", we have found a file!
if (s.contains(".")) {
result = curLen - 1 > result ? curLen - 1 : result;
}
}
return result;
}

private int countLevel(String s) {
String cur = s.replaceAll("\t", "");
return s.length() - cur.length();
}``````
X. Use HashMap
https://discuss.leetcode.com/topic/55245/concise-java-o-n-solution-use-map
Map to store the level and the length sum from root to current level.
level is calculated by how many 't' there.
length is preLevelLengthSum + current path length and ( + 1"/" if level bigger than 0)
``````public int lengthLongestPath(String input) {
String[] strs = input.split("\n");
int max = 0;
Map<Integer,Integer> map = new HashMap<>();
map.put(-1, 0);
for(int i = 0; i < strs.length; i++){
int level =  strs[i].lastIndexOf('\t')  + 1;
int length = map.get(level - 1) + strs[i].length() - level + (level > 0 ? 1 : 0);
if(strs[i].indexOf('.') == -1){
map.put(level, length);
}else{
max = Math.max(length, max);
}
}
return max;
}``````
https://discuss.leetcode.com/topic/55561/two-different-solutions-in-java-using-stack-and-hashmap
``````    public int lengthLongestPath2(String input) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
hashMap.put(0, 0);
int result = 0;
for (String s : input.split("\n")) {
int level = s.lastIndexOf("\t") + 1;
int len = s.substring(level).length();
if (s.contains(".")) {
result = Math.max(result, hashMap.get(level) + len);
} else {
hashMap.put(level + 1, hashMap.get(level) + len + 1);
}
}
return result;
}``````
https://discuss.leetcode.com/topic/56437/java-simple-solution
``````public int lengthLongestPath(String input) {
int longest = 0;
String[] lines = input.split("\n");
int[] lens = new int[lines.length+1];
for(String line: lines) {
String[] subs = line.split("\t");
String cur = subs[subs.length-1];
int len = lens[subs.length-1] + cur.length() + 1;
if(cur.contains(".")) longest = Math.max(longest, len-1);
else lens[subs.length] = len;
}
return longest;
}``````
X. http://ninefu.github.io/blog/388-Longest-Absolute-File-Path/
```    public int lengthLongestPath(String input) {
String[] lines = input.split("\n");
int[] length = new int[lines.length + 1];
int max = 0;

for (String line : lines) {
int depth = line.lastIndexOf("\t") + 1;
length[depth + 1] = length[depth] + 1 + line.length() - depth;
if (line.indexOf(".") != -1) {
max = Math.max(max, length[depth + 1] - 1);
}
}
return max;
}```

http://glassjar-blog.appspot.com/Article?aid=ag9zfmdsYXNzamFyLWJsb2dyFAsSB0FydGljbGUYgICAgLyfmwoM