在Java中找到每个组的最长公共祖先路径

Question

我试图在通用路径信息中找到每个组的最长共同祖先。下面是我的 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[key2=value2]/path4/leaf1,
/Module1:path1/path2/path3[key2=value2]/path4/leaf2,    
/Module3:path1/path2/path3[key3=value33]/path4/leaf2,
/Module3:path1/path2/path3[key3=*]/path4/leaf2,
/Module4:path1/path2[key4=value1]/path3[key5=value1]/path4/leaf2,
/Module4:path1/path2[key4=value1]/path3[key5=*]/path4/leaf2,
/Module5:path1/path2/path3/path4/leaf1]

从上面的列表中，我试图找到每个群体最长的共同祖先。条件如下：

1. 对每个模块的最长公共祖先路径进行分组。
2. 每条路径可能包含也可能不包含基于键/值的过滤器（它可能包含一个或多个键过滤器）。
3. 如果路径具有相同的密钥和相同的模块，则将它们分组在一起并找到最长的共同祖先路径。
4. 如果路径具有相同的模块但不同的键，请将它们视为单独的条目。
5. 如果键值指定为“*”，则将其视为适用于所有值。在这种情况下，排除该模块的关键条目并返回通用路径。
6. 排除叶节点（当路径被“/”分割时，叶节点始终是最后一个元素）。

我对上述输入期望的最终输出是

   [/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<String, List<String>> groupByModuleName(List<String> paths) {
    Map<String, List<String>> 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<String> pathInfo = moduleGroups.get(moduleName);
            pathInfo.add(truncatedPath);
            moduleGroups.put(moduleName, pathInfo);
        } else {
            List<String> pathInfo = new ArrayList<>();
            pathInfo.add(truncatedPath);
            moduleGroups.put(moduleName, pathInfo);
        }
    }
    return moduleGroups;
}

分组后，在 findCommonAncestorForGroup 方法中，我的逻辑是计算每个组的最长公共祖先路径。

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

在 findCommonAncestorForGroup 方法中，我尝试了几种方法来获得预期的输出，但其他一些用例正在崩溃。您对如何有效解决这个问题有什么建议吗？

请注意，模块和路径名称可以是任何名称。我使用了Module1、Module2等，只是为了简化我的查询

Answer 1

首先，您需要识别组。每个组由公共模块和公共密钥定义。因此，创建一个

Map<String, Map<String, List<String[]>>

是有意义的，其中外部

Map

的键是模块名称，内部

Map

的键是键，而

String

List

的元素是将是实际路径（由

/

分割）。到目前为止一切顺利。

第 1 步：创建主要组

循环路径，对于每个路径，查看模块是否已经在外部

Map

中，如果没有则创建它。然后看看这个

Module

的项目是否已经有

key

作为

key

。

当然，

Module

在第一个

:

的左侧，如果你

split

在

/

右侧，然后循环各个部分，你就可以找到关键是什么。因此，很清楚哪个

Module

的

key

是，因此添加该项目也很容易。

此时，不要担心

*

作为键，在

Map

内创建它，我们稍后会返回。

第二步：处理星星

循环外部

Map

，看看哪个内部

Map

的

key

为

*

。对于这些项目，循环其他内部键并将此

*

添加到它们中，因此，如果您有一个模块并且有一个带有

*

的项目，那么您可以将此项目附加到模块的所有组中，然后删除此项目

*

。如果您有多条带有

*

的路径，请避免将一颗星添加到另一颗星上。

第3步：找到最长的公共路径

既然您已经对组进行了排序，您可以循环每个模块并为每个键嵌套一个内部循环，其中您已经分割了字符串。看看前两个的第一个分割子串中有多少是公共的，那就是

c

。然后比较第一个和第三个的第一个

c

分割子串，如果第一个和第三个之间的共同点较少，则减少

c

，并以这种方式继续，直到到达组的末尾。知道

c

是什么，您可以推断出组中任何元素的第一个

c

分割的子字符串，并将它们与

/

作为分隔符粘合在一起，以达到您期望的结果。