Java中R-way trie最长公共前缀最优实现方案咨询

目标是递归遍历R-way Trie，找到至少作为两个字符串前缀的最长公共前缀，以及该前缀关联的字符串数量。Trie节点包含timesUsed属性，插入新字符串时，每次访问该节点都会递增此属性。

示例 #

输入：figure, fight, finger, english, entail
输出：

Longest prefix: fig
Number of Strings: 2

现有三种实现方案 #

方案一：收集所有符合条件的前缀后筛选 #

public void allPrefixes() {
    ArrayList<String> list = new ArrayList<>();
    ArrayList<Integer> timesUsed = new ArrayList<>();

    allPrefixesUtil(list, timesUsed, root, "");

    int longestPrefixIndex = getLongestIndex(list);

    System.out.println("Longest common prefix: " + list.get(longestPrefixIndex));
    System.out.println("Number of strings: " + timesUsed.get(longestPrefixIndex));
}

public void allPrefixesUtil(ArrayList<String> list, ArrayList<Integer> timesUsed, Node x, String s) {
    for (int i = 0; i < x.next.length; i++) {
        if (x.next[i] != null && x.next[i].timesUsed >= 2) {
            list.add(s + (char) (i + 'a'));
            timesUsed.add(x.next[i].timesUsed);
            allPrefixesUtil(list, timesUsed, x.next[i], s + (char) (i + 'a'));
        }
    }
}

问题：会将所有timesUsed≥2的前缀（如e, en, f, fi, fig）全部存入列表，空间占用较高，尤其当Trie规模大时，内存浪费明显。

方案二：直接跟踪最长前缀（解决值传递问题） #

最初尝试直接传递字符串和整数，但因Java值传递特性失效，改为使用单元素数组传递变量：

public void allPrefixes2() {
    String[] longest = { "" };
    int[] timesUsed = { 0 };

    allPrefixesUtil2(longest, timesUsed, root, "");

    System.out.println("Longest common prefix: " + longest[0]);
    System.out.println("Number of strings: " + timesUsed[0]);
}

public void allPrefixesUtil2(String[] longest, int[] timesUsed, Node x, String s) {
    for (int i = 0; i < x.next.length; i++) {
        Node nextNode = x.next[i];
        if (nextNode != null && nextNode.timesUsed >= 2) {
            String str = s + (char) (i + 'a');
            if (str.length() > longest[0].length()) {
                longest[0] = str;
                timesUsed[0] = nextNode.timesUsed;
            }
            allPrefixesUtil2(longest, timesUsed, nextNode, str);
        }
    }
}

疑问：此方案可行，但不确定是否为合理写法。

方案三：为Trie添加专用属性 #

给通用Trie节点或结构添加longest和timesUsed属性，直接在递归中更新。
问题：违反单一职责原则，给通用Trie结构增加了业务相关属性，破坏了其通用性，不符合设计逻辑。

最优方案分析与更优实现 #

方案优劣对比 #

1. 方案一：空间复杂度O(N)（N为符合条件的前缀总数），空间浪费严重，不推荐。
2. 方案三：污染通用Trie结构，违反设计原则，不推荐。
3. 方案二的数组写法：可行且空间效率高（仅维护当前最长前缀的信息），但代码可读性较差，数组的语义不够直观。

更优实现：自定义结果封装类 #

用面向对象的方式封装结果，替代单元素数组，代码更清晰、符合Java常规实践，同时保持O(1)的额外空间开销（除递归栈外），时间复杂度为O(M)（M为Trie总节点数），是最优的时间效率。

// 自定义结果封装类，仅用于本次查询的结果传递
private static class PrefixResult {
    String longestPrefix;
    int count;

    public PrefixResult() {
        this.longestPrefix = "";
        this.count = 0;
    }
}

public void findLongestValidPrefix() {
    PrefixResult result = new PrefixResult();
    traverseTrie(root, "", result);
    System.out.println("Longest prefix: " + result.longestPrefix);
    System.out.println("Number of Strings: " + result.count);
}

private void traverseTrie(Node node, String currentPrefix, PrefixResult result) {
    for (int i = 0; i < node.next.length; i++) {
        Node childNode = node.next[i];
        if (childNode != null && childNode.timesUsed >= 2) {
            String newPrefix = currentPrefix + (char) (i + 'a');
            // 更新最长前缀：只有当新前缀更长时才替换
            if (newPrefix.length() > result.longestPrefix.length()) {
                result.longestPrefix = newPrefix;
                result.count = childNode.timesUsed;
            }
            // 递归遍历子节点，继续寻找更长的符合条件的前缀
            traverseTrie(childNode, newPrefix, result);
        }
    }
}

实现优势 #

• 可读性强：PrefixResult类明确封装了需要跟踪的两个变量，语义清晰，比数组更符合Java的编码习惯。
• 空间高效：仅维护当前最长的前缀和对应的计数，无需存储所有符合条件的前缀。
• 无侵入性：不修改原Trie结构，保持其通用性，符合单一职责原则。

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