Longest Absolute File Path in Leetcode

Question

I solved the Longest Absolute File Path challenge from Leetcode.

The question is

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.

The approach used is very similar to the way one would do this by hand. This solution looks like it has a lot of if/else statements.

Could you please suggest a cleaner way to write this solution.

public static int LengthLongestPath(string input) { var prefixLength = new Dictionary < int,int > (); int countT = 0, lengthSoFar = 0, maxLength = 0; bool isFile = false; for (int i = 0; i < input.Length; i++) { if (input[i] == '\n') { if (prefixLength.ContainsKey(countT - 1)) { prefixLength[countT] = lengthSoFar + prefixLength[countT - 1] + 1; } else { prefixLength[countT] = lengthSoFar; } if (isFile == true) { maxLength = Math.Max(maxLength, prefixLength[countT]); isFile = false; } lengthSoFar = 0; ++i; countT = 0; while (input[i] == '\t') { ++countT; ++i; } --i; } else { ++lengthSoFar; if (input[i] == '.') { isFile = true; } } } // To handle cases where file occours in the end of the string. if (isFile == true) { if (prefixLength.ContainsKey(countT - 1)) { maxLength = Math.Max(maxLength, prefixLength[countT - 1] + lengthSoFar + 1); } else { maxLength = Math.Max(maxLength, lengthSoFar); } isFile = false; } return maxLength; } 

Answer 1

Well, it is a little bit late to answer this question but I will do it nevertheless, because it's winterbash!

I had a hard time to read your code because of the level of indentation. I would suggest using the default of 4 spaces instead of 1 space.

Another problem with the code had been at first glance the countT variable but just because of the name. Abbreviations makes the code so much harder to read and understand. If the variable would have been named countedTabs its purpose would have been cristal clear.

One should use var if the type is easy to see by the right hand side of the assignment.

Manipulating a loop variable (i) if one can avoid is a bad habit and can lead to hard to find bugs. A simple else if (input[i] == '\t') { ++countedTabs; } would have been the way to avoid this.

If one need to know if a key exists in a Dictionary<TKey, TValue>ContainsKey() is the way to go, but only if the possible value isn't needed. If one needs the value one should use Dictionary<TKey, TValue>.TryGetValue(TKey, out TValue) because accessing the value later by calling Dictionary<TKey, TValue>[TKey] will internal call the ContainsKey() as well.

Instead of doing if (booleanVariable == true) one should use if (booleanVariable). One doesn't need to compare a boolean to true because the result of the comparison is just a boolean value as well. That beeing said, you can safely remove the isFile = false; at the end of that if block because it won't be used anymore. A last word about this if: The comment you placed above the if is a good comment because it describes why you have the if in place.

One last point to make, don't declare multiple variables in one line. This just hurts the readability of the code.

Summing up leads to

public static int LengthLongestPath(string input) { var prefixLength = new Dictionary<int, int>(); var countedTabs = 0; var lengthSoFar = 0; var maxLength = 0; var isFile = false; for (var i = 0; i < input.Length; i++) { if (input[i] == '\n') { if (prefixLength.TryGetValue(countedTabs - 1, out int value)) { prefixLength[countedTabs] = lengthSoFar + value + 1; } else { prefixLength[countedTabs] = lengthSoFar; } if (isFile == true) { maxLength = Math.Max(maxLength, prefixLength[countedTabs]); isFile = false; } lengthSoFar = 0; countedTabs = 0; } else if (input[i] == '\t') { ++countedTabs; } else { ++lengthSoFar; if (input[i] == '.') { isFile = true; } } } // To handle cases where file occours in the end of the string. if (isFile) { if (prefixLength.TryGetValue(countedTabs - 1, out int value)) { maxLength = Math.Max(maxLength, value + lengthSoFar + 1); } else { maxLength = Math.Max(maxLength, lengthSoFar); } } return maxLength; }