Znajdowanie najdłuższej bezwzględnej ścieżki pliku przy użyciu java

Question

Zaimplementowałem następującą metodę, aby znaleźć najdłuższą absolutną ścieżkę pliku.

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; 
} 

Jest to jednak błąd dla następujących danych wejściowych. Oczekiwana moc wyjściowa to 528. Ale moja wydajność to 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" 

Czy ktoś może mi pomóc znaleźć problem z moim kodem.

Podanie informacji o formacie ciągu znaków Poniższy ciąg reprezentuje: następującą ścieżkę pliku.

"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

Uproszczenie istniejącego kodu daje następujące, która zwraca poprawny wynik dla obu swoich przykładach:

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

myślę może być nadmiernie komplikuje sprawy. Ze względu na format napisów nie można "wrócić" do już wyjechanego katalogu, więc nie trzeba przechowywać mapy. Alternatywny realizacja może być podzielić ciąg przez charakter \n i użyj listy, aby śledzić, gdzie jesteś na ścieżce, gdzie liczba \t znaków oznacza pozycję trzeba zachować:

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; 
}