Problem
Suppose we abstract our file system by a string in the following manners:
The string
dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext
represents:dir subdir1 subdir2 file.ext
a directory
dir
contains an empty sub-directoriessubdir1
and a sub-directorysubdir2
containing a filefile.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
a directory
dir
contains two sub-directoriessubdir1
andsubdir2
.subdir1
contains a filefile1.extand
an empty second-level sub-directorysubsubdir1
.subdir2
contains a second-level sub-directorysubsubdir2
containing a filefile2.ext
.We are interested in finding the longest (number of characters) absolute path to a file within our file system. That is, for example, in the second example above, the longest absolute path is
dir/subdr2/subsubdir2/file.ext
, and its length is 30.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. Simply put, that is the length of a valid path that ends with a file, and a file contains . and an extension.
Time complexity required: O(n) where n is the size of the input string.
Notice that
a/aa/aaa/file1.txt
is not the path you want, if there isaaaaaaaaaaaaaaaaaaaaa/sth.png
.
Any advice on code bugs, performance improvements in terms of algorithm time complexity, or code style advice is highly appreciated.
def find_longest_path(source):
items = source.split('\n')
prefix = []
prefix_length = []
max_length_so_far = -1
max_path_so_far = ''
for path in items:
i = 0
while path[i] == '\t':
i += 1
if len(prefix) > i:
prefix = prefix[:i]
prefix_length = prefix_length[:i]
prefix.append(path[i:])
prefix_length.append(len(path[i:]))
if sum(prefix_length) > max_length_so_far:
max_length_so_far = sum(prefix_length)
max_path_so_far = '/'.join(prefix)
return max_path_so_far
if __name__ == "__main__":
path_name = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
print find_longest_path(path_name)
path_name = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
print find_longest_path(path_name)