本文介绍如何在java中对一组路径字符串进行智能分组，提取每组内元素的最长公共路径前缀，并确保结果去重且符合层级匹配逻辑。
本文介绍如何在java中对一组路径字符串进行智能分组，提取每组内元素的最长公共路径前缀，并确保结果去重且符合层级匹配逻辑。
在处理文件系统路径、URL路由或配置项层级结构时，常需从多个相似路径中识别出“语义上成组”的公共前缀。与简单求所有字符串的全局最长公共前缀（LCP）不同，本问题要求：将路径按首级目录（如 /partA、/partD）聚类，对每组内路径计算层级对齐的最长公共前缀，最终返回各组代表路径的唯一集合。
核心思路是基于路径分层结构（而非字符序列）进行比较。直接使用 String.substring() 逐字符比对会错误截断路径边界（例如把 /partG/partH 和 /partG/value2 错误匹配为 /partG/），而应以 / 为界拆分为目录片段（token），再逐段比对。
以下为完整实现：
import java.util.*;
import java.util.stream.Collectors;
public class LongestCommonPath {
public static void main(String[] args) {
String[] arr = {
"/partA/partB/partC/value1",
"/partA/partB/partC/value2",
"/partD/partE/partF/value1",
"/partD/partE/partF/value2",
"/partG/partH/partI/value1",
"/partG/value2",
"/partJ/value1"
};
List<String> result = longestCommonPaths(0, "/", arr);
System.out.println(result); // 输出: [/partA/partB/partC, /partD/partE/partF, /partG, /partJ/value1]
}
/**
* 提取路径数组中每组（按首段标识）的最长公共路径前缀
* @param offset 起始比较位置（通常为0，表示从根路径开始）
* @param delimiter 路径分隔符（如 "/"）
* @param paths 待处理路径数组
* @return 去重后的公共前缀列表（保持输入顺序）
*/
public static List<String> longestCommonPaths(int offset, String delimiter, String... paths) {
if (paths.length == 0) return Collections.emptyList();
// 步骤1：预处理——将每个路径按分隔符切分为 token 列表（保留空首段，如 "/a" → ["", "a"]）
List<List<String>> tokenized = Arrays.stream(paths)
.map(path -> tokenizePath(path, delimiter))
.collect(Collectors.toList());
Set<String> result = new LinkedHashSet<>(); // 保证插入顺序且去重
// 步骤2：对每个路径，寻找至少一个“伙伴路径”（同组），计算其最长公共前缀
for (int i = 0; i < tokenized.size(); i++) {
List<String> curr = tokenized.get(i);
boolean hasMatch = false;
// 遍历其他路径寻找匹配
for (int j = 0; j < tokenized.size(); j++) {
if (i == j) continue;
List<String> other = tokenized.get(j);
// 关键逻辑：仅当首段（offset=0时即第一个非空段）相同时才视为同组
// 这里简化为：若 curr 和 other 在 offset 位置的 token 相同，则参与 LCP 计算
if (curr.size() > offset && other.size() > offset
&& Objects.equals(curr.get(offset), other.get(offset))) {
List<String> common = commonPath(curr, other);
String joined = String.join(delimiter, common);
result.add(joined);
hasMatch = true;
}
}
// 若无任何匹配路径（孤立路径），则自身作为结果
if (!hasMatch) {
String joined = String.join(delimiter, curr);
result.add(joined);
}
}
return new ArrayList<>(result);
}
/**
* 计算两个 token 列表的最长公共前缀（逐段比对）
*/
private static List<String> commonPath(List<String> a, List<String> b) {
int len = Math.min(a.size(), b.size());
int index = 0;
while (index < len && Objects.equals(a.get(index), b.get(index))) {
index++;
}
return a.subList(0, index);
}
/**
* 将路径字符串按分隔符拆分为 token 列表（兼容开头的 "/"）
*/
private static List<String> tokenizePath(String path, String delimiter) {
// 使用 split 的负数 limit 参数保留末尾空字符串，但需手动处理开头
if (path.startsWith(delimiter)) {
String[] parts = path.substring(1).split(delimiter, -1);
List<String> tokens = new ArrayList<>();
tokens.add(""); // 根路径标记
tokens.addAll(Arrays.asList(parts));
return tokens;
} else {
return Arrays.stream(path.split(delimiter, -1))
.collect(Collectors.toList());
}
}
}✅ 关键设计说明：
Java Maven Common
下载
Java Maven 项目审查工作流的通用输入处理。当 Java Maven 项目以 ZIP压缩包或 GitLab 仓库 URL 形式提供且需要...时使用。
立即学习“Java免费学习笔记（深入）”；
-
层级安全比对：
tokenizePath精确处理路径开头的/，生成["", "partA", "partB", ...]结构，使commonPath可靠执行段级匹配； -
组判定逻辑：通过
offset参数控制分组依据（默认0表示按首段分组），避免跨组误匹配（如/partA/...与/partD/...不会比较）； -
去重与保序：使用
LinkedHashSet收集结果，既消除重复项，又维持首次发现顺序； -
边界健壮性：支持空路径、单段路径（如
/partJ/value1）及深度不一致路径（如/partG/partH/...vs/partG/value2）。
⚠️ 注意事项：
- 该算法时间复杂度为 O(n²·m)，其中 n 是路径数量，m 是平均路径段数，适用于中小规模数据（
- 若需高性能或大数据量场景，建议改用 Trie 树预构建路径索引；
- 实际应用中，可根据业务定义更严格的“同组”规则（例如要求前两段均相同），只需调整
offset或增加多段校验即可。
通过此方案，您能准确、可扩展地从杂乱路径中提炼出结构化的公共前缀集合，为路由聚合、权限路径归类或配置模板生成提供坚实基础。
