本文介绍一种高效方法，用于从路径字符串数组中识别并提取每组具有相同起始路径的元素的最长公共前缀（按目录层级匹配），最终返回去重后的唯一公共路径列表。
本文介绍一种高效方法，用于从路径字符串数组中识别并提取每组具有相同起始路径的元素的最长公共前缀（按目录层级匹配），最终返回去重后的唯一公共路径列表。
在处理文件系统路径、URL 路由或分层标识符时，常需从一组字符串中提取“逻辑分组”的最长公共路径前缀。与普通最长公共子串（LCS）不同，本场景强调按路径层级（即 / 分割后的目录段）对齐匹配，且目标是为每个“语义组”（如共享同一根目录的路径）生成一个最深可达的公共前缀。
例如，给定数组：
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"
};期望输出为：
["/partA/partB/partC", "/partD/partE/partF", "/partG", "/partJ/value1"]
关键在于：不是全局两两比对所有字符串，而是按“首级目录”（如 partA, partD）聚类，再在同类内求最长公共前缀。原始代码中直接逐字符比较 s1.charAt(idx) == s2.charAt(idx) 会错误匹配跨层级的字符（如 /partG/ 和 /partG/partH/ 在 /partG/v... 处因 v vs p 提前中断），无法体现路径结构语义。
立即学习“Java免费学习笔记（深入）”；
Java Maven Common
下载
Java Maven 项目审查工作流的通用输入处理。当 Java Maven 项目以 ZIP压缩包或 GitLab 仓库 URL 形式提供且需要...时使用。
✅ 正确解法分三步：
-
路径分词（Tokenization）：使用
split("/")将每个路径拆分为无空字符串的目录段列表（注意过滤首尾空项）； -
层级化比对：对每条路径，仅与首级目录相同的其他路径进行逐段比对（
path.get(0).equals(other.get(0))），避免跨组干扰； -
动态截取公共前缀：调用
commonPath()方法，遍历两路径的目录段，直到某索引处不相等，截取subList(0, index)并拼接为路径字符串。
以下是优化后的完整实现（修复了原答案中潜在的空指针与逻辑缺陷，并增强鲁棒性）：
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("/", arr);
System.out.println(result); // 输出: [/partA/partB/partC, /partD/partE/partF, /partG, /partJ/value1]
}
/**
* 提取数组中各组路径的唯一最长公共前缀（按首级目录分组）
* @param delimiter 路径分隔符（如 "/"）
* @param paths 待处理路径数组
* @return 去重后的公共前缀列表（保持首次出现顺序）
*/
public static List<String> longestCommonPaths(String delimiter, String... paths) {
if (paths == null || paths.length == 0) return Collections.emptyList();
// 1. 分词：对每个路径 split 并过滤空字符串（处理开头 "/" 导致的首空项）
List<List<String>> tokenized = Arrays.stream(paths)
.map(path -> Arrays.stream(path.split(delimiter))
.filter(s -> !s.isEmpty())
.collect(Collectors.toList()))
.collect(Collectors.toList());
Set<String> uniqueResult = new LinkedHashSet<>();
// 2. 对每条路径，寻找同组（首段相同）的其他路径
for (int i = 0; i < tokenized.size(); i++) {
List<String> curr = tokenized.get(i);
String firstSegment = curr.isEmpty() ? "" : curr.get(0);
boolean matched = false;
// 遍历其他路径找同组
for (int j = 0; j < tokenized.size(); j++) {
if (i == j) continue;
List<String> other = tokenized.get(j);
if (!other.isEmpty() && firstSegment.equals(other.get(0))) {
// 同组 → 计算最长公共前缀
List<String> common = commonPath(curr, other);
String joined = common.isEmpty() ? "" :
common.stream().collect(Collectors.joining(delimiter, "/", ""));
uniqueResult.add(joined);
matched = true;
}
}
// 3. 若未匹配到同组路径，保留原路径（作为独立项）
if (!matched && !curr.isEmpty()) {
String original = curr.stream()
.collect(Collectors.joining(delimiter, "/", ""));
uniqueResult.add(original);
}
}
return new ArrayList<>(uniqueResult);
}
/** 返回两个路径分词列表的最长公共前缀（按段匹配） */
private static List<String> commonPath(List<String> a, List<String> b) {
int len = Math.min(a.size(), b.size());
int idx = 0;
while (idx < len && a.get(idx).equals(b.get(idx))) {
idx++;
}
return a.subList(0, idx);
}
}? 注意事项：
- ✅ 使用
LinkedHashSet保证结果顺序与首次发现顺序一致； - ✅ 显式过滤
split("/")产生的空字符串（如"/a".split("/")得["", "a"]），避免首段误判； - ❌ 原答案中
currPath.get(offset)的offset=1参数设计有歧义且易出错，本实现统一以首段（index=0）为分组键，更符合题意中partA/partD/partG/partJ的分组逻辑； - ⚠️ 时间复杂度为 O(n²·m)，其中 n 为路径数，m 为平均段数；对大规模数据可考虑先哈希分组再内部比对以优化至 O(n·m)。
该方案精准建模了“路径层级公共前缀”问题，兼顾可读性、健壮性与业务语义，适用于日志归类、API 路由聚合、资源目录管理等真实场景。
