Longest Absolute Path File – Solved

I looked at the following LeetCode challenge:  https://leetcode.com/problems/longest-absolute-file-path/?tab=Description

Typically I write my test code using the Scanner class. Initially this time was no exception. I did notice that the input contained the strings “\n” and “\t” but I just went ahead. Processing of input created some side effects which I documented in a previous post with this same title. The approach which I will start using from now on was to place the input in an array of Strings and traverse it. This is illustrated in the following Java test code:

/**

* TEST code.

*/

public static void main(String[] args) {

// **** display system info ****

System.out.println(“main <<<                   os ==>” + System.getProperty(“os.name”) + “<==”);

System.out.println(“main <<< java.runtime.version ==>” + System.getProperty(“java.runtime.version”) + “<==”);

System.out.println();

// **** test strings ****

              String[] fs =        {

                           “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”,

“dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”,

                           “dir\n\tsubdir1\n\tsubdir2\n\tsubdir3”,

                           “dir\n\t        file.txt\n\tfile2.txt”,               

                           “dir\n\t    file.txt”,

                           “dir\n    file.txt”,

                           “dir\n\t    file.txt”,

                           “dir\n    file.txt”,

                           “dir\n\tfile.txt”,

                           “dir\nfile.txt”,

                           “dir\n        file.txt”

                           };

// **** ****

for (String p : fs) {

// **** display current file system path ****

System.out.println(p);

// **** length of the longest absolute path to file ****

System.out.println(“main <<< ” + lengthLongestPath(p));

}

}

I also decided to start displaying the Java version and the OS. I know which machine I am using, but for readers it is good to know which OS and tools I am using.

I made a change to the requirements. They call for the function to just display the length of the longest path. I wanted to generate each path, get the associated length and then determine if it was the longest so far. Perhaps a little more work but it makes it easy to determine if the process is working.

Following is a screen capture of the console from the Eclipse IDE running the test cases provided in the challenge, some from test cases and some that I made up:

main <<<                   os ==>Windows 10<==

main <<< java.runtime.version ==>1.8.0_121-b13<==

dir

subdir1

subdir2

file.ext

lengthLongestPath <<< fullPath ==>dir/subdir2/file.ext<== maxLength: 20

main <<< 20

dir

subdir1

file1.ext

subsubdir1

subdir2

subsubdir2

file2.ext

lengthLongestPath <<< fullPath ==>dir/subdir1/file1.ext<== maxLength: 21

lengthLongestPath <<< fullPath ==>dir/subdir2/subsubdir2/file2.ext<== maxLength: 32

main <<< 32

dir

subdir1

subdir2

subdir3

main <<< 0

dir

file.txt

file2.txt

lengthLongestPath <<< fullPath ==>dir/        file.txt<== maxLength: 20

lengthLongestPath <<< fullPath ==>dir/file2.txt<== maxLength: 20

main <<< 20

dir

file.txt

lengthLongestPath <<< fullPath ==>dir/    file.txt<== maxLength: 16

main <<< 16

dir

file.txt

lengthLongestPath <<< fullPath ==>    file.txt<== maxLength: 12

main <<< 12

dir

file.txt

lengthLongestPath <<< fullPath ==>dir/    file.txt<== maxLength: 16

main <<< 16

dir

file.txt

lengthLongestPath <<< fullPath ==>    file.txt<== maxLength: 12

main <<< 12

dir

file.txt

lengthLongestPath <<< fullPath ==>dir/file.txt<== maxLength: 12

main <<< 12

dir

file.txt

lengthLongestPath <<< fullPath ==>file.txt<== maxLength: 8

main <<< 8

dir

file.txt

lengthLongestPath <<< fullPath ==>        file.txt<== maxLength: 16

main <<< 16

There was some confusion (myself included) regarding regular files (not directories) in the same folder as the root. You can take a look at the discussions in the LeetCode web site. The simple approach was to use the level of the files when generating the full paths.

Following is the test code for my solution which was accepted:

/**

* Determine if this path is a directory.

*/

static boolean isDirectory(String path) {

return !path.contains(“.”);

}

/**

* Determine the path level.

*/

static int pathLevel(String name) {

String[] split = name.split(“\t”);

return split.length – 1;

}

/**

* Build full path for specified file at specified level.

*/

static String buildFullPath(Stack<String> pathStack, int level, String fileName) {

String fullPath = “”;

for (int i = 0; i < level; i++) {

fullPath += pathStack.elementAt(i);

fullPath += “/”;

}

fullPath += fileName;

return fullPath;

}

/**

* Use (and display) the actual path to generate it’s length.

*/

static int lengthLongestPath(String input) {

int maxLength              = 0;

int currentLevel           = 0;

Stack<String> pathStack    = new Stack<String>();

int level;

// **** split input into relative paths and file names ****

String[] paths = input.split(“\n”);

// **** ****

for (String s : paths) {

// **** compute the path level ****

level = pathLevel(s);

// **** remove \t from file name ****

s = s.replaceAll(“\t”, “”);

// **** this is a directory ****

if (isDirectory(s)) {

// **** adjust the directory path stack ****

for ( ; currentLevel > level; currentLevel–) {

pathStack.pop();

}

// **** push current directory and adjust current directory level ****

pathStack.push(s);

currentLevel++;

}

// **** this is a file ****

else {

// **** build the full path of the file ****

String fullPath = buildFullPath(pathStack, level, s);

// **** compute the length and update the max length (if needed) ****

int len = fullPath.length();

if (len > maxLength) {

maxLength = len;

}

System.out.println(“lengthLongestPath <<< fullPath ==>” + fullPath + “<== maxLength: ” + maxLength);

}

}

// **** return the length of the max path ****

return maxLength;

}

The main function makes use of three additional methods. One of them is a single liner which may or may not be needed but I just went ahead and added it to the solution.

The pathLevel() function was initially named directoryLevel(). The reason was that I was interested in keeping track of directories in the stack. The problem was that I had problems generating the correct full paths for files; in particular for files at the same level as the main directory.  I changed the name of the function and added the level argument to the buildFullPath() function.

If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.