leetcode LongestAbsoluteFilePath
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.List;
import java.util.Stack;

public class LongestAbsoluteFilePath {
  /**
   * 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.
   */
  public static int lengthLongestPath(String input) {
    Stack<Integer> stack = new Stack<>();
    String[] l = input.split("\\n");
    stack.push(0);
    int maxLength = 0;
    int temp = 0;
    for (String s: l){
      int inx = s.lastIndexOf("\\t")+1;
      while (inx+1 < stack.size()){
        stack.pop();
      }
      temp = stack.peek() + s.length() - inx + 1; // 后面的+1是针对dir时，后面需要再添加上一个'/'
      stack.push(temp);
      if (s.contains("."))
        maxLength = Math.max(maxLength, temp-1); // 对于文件，把之前添加上的'/'去掉，所以要-1
    }
    return maxLength;
  }

}