Finding the longest absolute file path using java

Question

I applied the following method to find the longest path of an absolute file.

public static int lengthLongestPath(String input) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); if (input.length() == 0) return 0; int maxLength = 0; int subStringLength = 0; int previousLevel = 0; String[] paths = input.split("\n"); for (String path : paths) { String[] substr = path.split("\t"); String dirOrFile = substr[substr.length-1]; int level = substr.length -1; if(level <= previousLevel && level !=0){ previousLevel = level-1; subStringLength = map.get(previousLevel); }else if(level ==0){ subStringLength = 0; }else{ previousLevel = level; } subStringLength += dirOrFile.length(); if(dirOrFile.contains(".")){ maxLength = Math.max(subStringLength+level, maxLength); } map.put(level, subStringLength); } return maxLength; } 

However, it does not work for the next input. The expected result is 528. But my result is 549.

 "sladjf\n\tlkjlkv\n\t\tlkjlakjlert\n\t\t\tlaskjglaksjf\n\t\t\t\tlakjgfljrtlj\n\t\t\t\t\tlskajflakjsvlj\n\t\t\t\t\t\tlskgjflkjrtlrjt\n\t\t\t\t\t\t\tlkjglkjlvkjdlvkj\n\t\t\t\t\t\t\t\tlfjkglkjfljdlv\n\t\t\t\t\t\t\t\t\tlkdfjglerjtkrjkljsd.lkvjlkajlfk\n\t\t\t\t\t\t\tlskfjlksjljslvjxjlvkzjljajoiwjejlskjslfj.slkjflskjldfkjoietruioskljfkljf\n\t\t\t\t\tlkasjfljsaljlxkcjzljvl.asljlksaj\n\t\t\t\tasldjflksajf\n\t\t\t\talskjflkasjlvkja\n\t\t\t\twioeuoiwutrljsgfjlskfg\n\t\t\t\taslkjvlksjvlkjsflgj\n\t\t\t\t\tlkvnlksfgk.salfkjaslfjskljfv\n\t\t\tlksdjflsajlkfj\n\t\t\tlasjflaskjlk\n\t\tlsakjflkasjfkljas\n\t\tlskjvljvlkjlsjfkgljfg\n\tsaljkglksajvlkjvkljlkjvksdj\n\tlsakjglksajkvjlkjdklvj\n\tlskjflksjglkdjbkljdbkjslkj\n\t\tlkjglkfjkljsdflj\n\t\t\tlskjfglkjdfgkljsdflj\n\t\t\t\tlkfjglksdjlkjbsdlkjbk\n\t\t\t\t\tlkfgjlejrtljkljsdflgjl\n\t\t\t\t\tsalgkfjlksfjgkljsgfjl\n\t\t\t\t\tsalkflajwoieu\n\t\t\t\t\t\tlaskjfglsjfgljkkvjsdlkjbklds\n\t\t\t\t\t\t\tlasjglriotuojgkjsldfgjsklfgjl\n\t\t\t\t\t\t\t\tlkajglkjskljsdljblkdfjblfjlbjs\n\t\t\t\t\t\t\t\t\tlkajgljroituksfglkjslkjgoi\n\t\t\t\t\t\t\t\t\t\tlkjglkjkljkljdkbljsdfljgklfdj\n\t\t\t\t\t\t\t\t\t\t\tlkjlgkjljgslkdkldjblkj\n\t\t\t\t\t\t\t\t\t\t\t\tlkjfglkjlkjbsdklj.slgfjalksjglkfjglf\n\t\t\t\t\t\t\t\t\t\t\t\tlkasjrlkjwlrjljsl\n\t\t\t\t\t\t\t\t\t\t\t\t\tlksjgflkjfklgjljbljls\n\t\t\t\t\t\t\t\t\t\t\t\t\t\tlkjsglkjlkjfkljdklbjkldf\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tlkjglkjdlsfjdglsdjgjlxljjlrjsgjsjlk\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tlkjsgkllksjfgjljdslfkjlkasjdflkjxcljvlkjsgkljsfg\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tlaskjlkjsakljglsdjfgksdjlkgjdlskjb\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tlkajsgfljfklgjlkdjgfklsdjklj\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tlkjfglkjlkgjlkjl.aslkjflasjlajglkjaf\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tlkjasflgjlskjglkfjgklgsdjflkbjsdklfjskldfjgklsfdjgklfdjgl\n\tlskadjlkjsldwwwwwfj\n\t\tlkjflkasjlfjlkjajslfkjlasjkdlfjlaskjalvwwwwwwwwwwwwwwwkjlsjfglkjalsjgflkjaljlkdsjslbjsljksldjlsjdlkjljvblkjlkajfljgasljfkajgfljfjgldjblkjsdljgsldjg.skljf" 

Can someone help me find a problem with my code.

To give some information about the format of the line, the next line represents the next path to the file.

 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" dir subdir1 file1.ext subsubdir1 subdir2 subsubdir2 file2.ext 

Answer 1

Simplifying your existing code yields the following, which returns the correct result for both of your examples:

 public static int lengthLongestPath(String input) { if (input.length() == 0) return 0; Map<Integer, Integer> map = new HashMap<>(); int maxLength = 0; String[] paths = input.split("\n"); for (String path : paths) { String dirOrFile = path.replaceFirst("\\t*", ""); int level = path.lastIndexOf("\t") + 1; int prefixLength = 0; if (level > 0) { prefixLength = map.get(level - 1); } int pathLength = prefixLength + dirOrFile.length(); if (dirOrFile.contains(".")) { maxLength = Math.max(pathLength + level, maxLength); } map.put(level, pathLength); } return maxLength; } 

Answer 2

I think you can make things too complicated. Due to the format of the line, you cannot “return” to the directory that you already left, so you do not need to save the map. An alternative implementation would be to split the string into the \n character and use a list to keep track of where you are on the path, where the number of characters \t stands for the position you need to keep:

 public static int lengthLongestPath(String input) { int maxLen = 0; List<String> currPath = new LinkedList<>(); String[] parts = input.split("\n"); for (String part : parts) { int numTabs = Math.max(0, part.lastIndexOf('\t')); part = part.substring(numTabs + 1); currPath = currPath.subList(0, numTabs); currPath.add(part); int curLen = currPath.stream().mapToInt(String::length).sum(); maxLen = Math.max(maxLen, curLen); } return maxLen; }