/**
* 388. Longest Absolute File Path
* Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1
* contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file * file2.ext.
* In text form, it looks like this (with ⟶ representing the tab character):
* dir ⟶ subdir1 ⟶ ⟶ file1.ext ⟶ ⟶ subsubdir1 ⟶ subdir2 ⟶ ⟶ subsubdir2 ⟶ ⟶ ⟶ file2.ext If we were to write this representation in code, it will look like this: “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”.
* Note that the ‘\n’ and ‘\t’ are the new-line and tab characters.
*
* Every file and directory has a unique absolute path in the file system, which is the order of directories that must
* be opened to reach the file/directory itself, all concatenated by ‘/’s. Using the above example, the absolute path to
* file2.ext is “dir/subdir2/subsubdir2/file2.ext”. Each directory name consists of letters, digits, and/or spaces. Each
* file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.
*
* Example 1:
*
* Input: input = “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”
* Output: 20
* Explanation: We have only one file, and the absolute path is “dir/subdir2/file.ext” of length 20.
* Example 2:
*
* Input: input = “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”
* Output: 32
* Explanation: We have two files:
* “dir/subdir1/file1.ext” of length 21
* “dir/subdir2/subsubdir2/file2.ext” of length 32.
* We return 32 since it is the longest absolute path to a file.
*/
See the solution on github at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/LongestAbsoluteFilePath.java
Observation:
Each subdirectory is delimited by the newline character “\n”. The depth of the directory is specified by the number of tab characters after the new line character “\t”. We could split the string by newline characters to have each string specify one directory. Second, by structure of the problem we would have directories with less depth come before those with increased depth. Therefore, we can calculate the longest file path based on length in prior level and add to it the length of current file name.
Logic is:
- Split the string by ‘\n’ newline characters
- For each substring find the index of the last tab in it, this will indicate the depth of directory or file at that level.
- We can identify whether a file or directory based on whether the string contains the character ‘.’
- We can store the length of the file path per level so far in an array
- The new levels length can be based off of the prior length and adding length of current directory to it
Here is the code:
public int lengthLongestPath(String input) {
int maxPathSize = 0;
String[] paths = input.split("\n");
ArrayList<Integer> levelLengths = new ArrayList<>();
levelLengths.ensureCapacity(20);
for (String path : paths) {
int level = path.lastIndexOf("\t") + 1; //add 1 to handle case where the method returns -1
String name = path.substring(level);
int priorLength = level == 0 ? 0 : levelLengths.get(level - 1);
if (name.contains(".")) {
int currLen = priorLength + name.length();
maxPathSize = Math.max(maxPathSize, currLen);
} else {
if (levelLengths.size() < level + 1) {
levelLengths.add(0);
}
levelLengths.set(level, priorLength + name.length() + 1);
}
}
return maxPathSize;
}