Java中提取数组分组最长公共前缀的实现问题

问题说明 #

给定字符串数组：

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"
]

当前用逐字符比较的方式无法得到预期结果，以下是可行的实现方案。

实现思路与代码 #

核心逻辑 #

1. 拆分路径段：把每个字符串按/拆分成路径片段数组，方便按层级处理前缀
2. 构建前缀树：用前缀树存储所有路径片段，每个节点记录经过该节点的路径数量——这个计数是判断公共前缀范围的关键
3. 遍历提取结果：从根节点往下遍历，遇到以下情况就停止并记录结果：
   • 当前节点的子节点计数小于2（再往下没有共同前缀了）
   • 当前节点计数为1（说明是孤立路径，直接取原字符串）

Java 实现代码 #

import java.util.*;

class TrieNode {
    // 存储子节点，键为路径片段
    Map<String, TrieNode> children = new HashMap<>();
    // 记录有多少条路径经过该节点
    int count = 0;
}

public class LongestCommonPrefixGroup {
    public static List<String> extractGroupedPrefixes(String[] arr) {
        TrieNode root = new TrieNode();
        
        // 第一步：构建前缀树
        for (String path : arr) {
            String[] segments = path.split("/");
            TrieNode current = root;
            for (String seg : segments) {
                current.children.putIfAbsent(seg, new TrieNode());
                current = current.children.get(seg);
                current.count++;
            }
        }
        
        // 第二步：遍历前缀树提取结果
        List<String> result = new ArrayList<>();
        traverseTrie(root, new ArrayList<>(), result, arr);
        return result;
    }
    
    private static void traverseTrie(TrieNode node, List<String> currentPath, List<String> result, String[] originalArr) {
        // 处理孤立路径：计数为1说明只有一条路径到这里，直接找原字符串
        if (node.count == 1) {
            String prefix = String.join("/", currentPath);
            for (String path : originalArr) {
                if (path.startsWith(prefix) && path.split("/").length == currentPath.size()) {
                    result.add(path);
                    break;
                }
            }
            return;
        }
        
        // 遍历所有子节点
        for (Map.Entry<String, TrieNode> entry : node.children.entrySet()) {
            String seg = entry.getKey();
            TrieNode child = entry.getValue();
            currentPath.add(seg);
            
            // 如果子节点计数小于2，当前路径就是最长公共前缀
            if (child.count < 2) {
                result.add(String.join("/", currentPath));
            } else {
                // 子节点还有多条路径，继续往下遍历
                traverseTrie(child, currentPath, result, originalArr);
            }
            
            // 回溯路径
            currentPath.remove(currentPath.size() - 1);
        }
    }
    
    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> prefixes = extractGroupedPrefixes(arr);
        System.out.println(prefixes);
    }
}

代码解释 #

• 前缀树节点：用HashMap存储子节点，适配任意路径片段；count字段标记路径经过次数，用来判断是否是公共前缀的终点
• 构建阶段：把每个路径拆成片段后逐个插入前缀树，每经过一个节点就把计数加1
• 提取阶段：
  • 遇到count=1的节点，说明这是唯一路径，找到对应的原字符串加入结果
  • 子节点count<2时，当前路径就是该组的最长公共前缀，拼接后加入结果
  • 否则继续深入遍历，直到满足停止条件

内容的提问来源于stack exchange，提问作者Prasad