Recursion Problem
Time Complexity: O(N) N is number of words in input
def lengthLongestPath(input):
filepathes = []
path = []
foo(input.split("\n"), 0, path, filepathes)
if len(filepathes) == 0:
return 0
lens = map(lambda path: len(path), filepathes)
print(filepathes)
return max(lens)
def foo(arr, index, path, filepathes):
if len(arr) == index:
return
depth = arr[index].count("\t")
dirname = arr[index].strip("\t")
if path:
rootpath = path[:depth]
else:
rootpath = []
if arr[index].find(".") != -1:
filename = arr[index].strip("\t")
rootpath.append(filename)
filepathes.append('/'.join(rootpath))
rootpath.pop()
foo(arr, index + 1, rootpath, filepathes)
#return
else:
rootpath.append(dirname)
foo(arr, index + 1, rootpath, filepathes)
input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" # 20
print(lengthLongestPath(input))
input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" # 32
print(lengthLongestPath(input))
input = "file1.txt\nfile2.txt\nlongfile.txt" # 12
print(lengthLongestPath(input))
input ="dir\n file.txt"
print(lengthLongestPath(input)) # 16