Найдите самый длинный общий путь предка для каждой группы в Java ⇐ JAVA

[Anonymous]

Я пытаюсь найти самого длинного общего предка для каждой группы в информации об общем пути. Ниже приведен мой список ввода типа String

Код: Выделить всё

[/Module1:path1/path2/path3[key1=value1]/path4/leaf1,
/Module1:path1/path2/path3[key1=value1]/path4/leaf2,
/Module1:path1/path2/path3[key1=value1]/path5/leaf1,
/Module1:path1/path2/path3[key=value2]/path4/leaf1,
/Module1:path1/path2/path3[key=value2]/path4/leaf2,
/Module2:path1/path2/path3[key=value22]/path4/leaf2,
/Module3:path1/path2/path3[key=value33]/path4/leaf2,
/Module3:path1/path2/path3[key=*]/path4/leaf2,
/Module4:path1/path2[key=value1]/path3[key=value1]/path4/leaf2,
/Module4:path1/path2[key=value1]/path3[key=value2]/path4/leaf2,
/Module5:path1/path2/path3/path4/leaf1]

Из приведенного выше списка я пытаюсь найти самого длинного общего предка для каждой группы. Ниже приведены условия:

• Сгруппируйте самый длинный общий путь предка для каждого модуля.
• Каждый путь может содержать или не содержать фильтры на основе ключа/значения (он может содержать один или несколько ключевых фильтров).
• Если путь имеет одинаковый ключ и один и тот же модуль, сгруппируйте их вместе и найдите самый длинный общий путь предка. .
• Если путь имеет один и тот же модуль, но разные ключи, рассматривайте их как отдельные записи.
• Если значение ключа указано как «*», рассматривайте его как применимое ко всем значениям. В этом случае исключите ключевые записи для этого модуля и верните общий путь.
  Исключите конечные узлы (которые всегда являются последним элементом, если путь разделен знаком «/»).< /li>

Окончательный результат, который я ожидаю от приведенного выше ввода, будет

Код: Выделить всё

   [/Module1:path1/path2/path3[key1=value1],
/Module1:path1/path2/path3[key2=value2]/path4,
/Module3:path1/path2/path3[key3=*]/path4/leaf2,
/Module4:path1/path2[key4=value1]/path3[key5=*]/path4/leaf2,
/Module5:path1/path2/path3/path4/leaf1]

Я попробовал несколько способов и смог найти самый длинный общий путь предка, не принимая во внимание ключи. Однако включение ключей возвращает неожиданный результат. Как лучше всего эффективно решить эту проблему?
Ниже приведен мой код для группировки по модулю и исключения конечных значений.

Код: Выделить всё

 private static Map groupByModuleName(List paths) {
Map moduleGroups = new HashMap();
for (String path : paths) {
String[] components = path.split("/");
String moduleName = components[0] + "/" + components[1];
String truncatedPath = String.join("/", Arrays.copyOf(components, components.length - 1));
if (moduleGroups.containsKey(moduleName)) {
List pathInfo = moduleGroups.get(moduleName);
pathInfo.add(truncatedPath);
moduleGroups.put(moduleName, pathInfo);
} else {
List pathInfo = new ArrayList();
pathInfo.add(truncatedPath);
moduleGroups.put(moduleName, pathInfo);
}
}
return moduleGroups;
}

После группировки, в методе findCommonAncestorForGroup моя логика для расчета самого длинного общего пути предка для каждой группы.

Код: Выделить всё

    Map moduleGroups = groupByModuleName(paths);
List result = new ArrayList();
for (Map.Entry entry : moduleGroups.entrySet()) {
List groupPaths = entry.getValue();
String commonAncestor = findCommonAncestorForGroup(groupPaths);
result.add(commonAncestor);
}
return result;

В методе findCommonAncestorForGroup я попробовал несколько способов получить ожидаемый результат, но некоторые другие варианты использования не работают. Есть ли у вас какие-либо предложения по эффективному решению этой проблемы?
Обратите внимание, что имена модулей и путей могут быть любыми. Я использовал Module1, Module2 и т. д., просто чтобы упростить запрос

Подробнее здесь: https://stackoverflow.com/questions/792 ... up-in-java