基于Trie实现LeetCode最长公共前缀，单字符单输入用例失败排查

你的代码在输入{"a"}时测试失败，主要有两个核心问题：

1. 静态成员导致的跨测试用例状态污染 #

你的代码中root是静态变量，insertNode和longestCommonPrefix也是静态方法。在LeetCode的测试环境中，Solution类只会被加载一次，静态变量会在多次测试用例之间保留之前的状态。比如如果之前的测试用例已经插入过其他字符串，root的childCount可能大于1，此时再测试{"a"}，longestCommonPrefix会直接返回空字符串。

2. 未处理单词结束节点的判断 #

longestCommonPrefix的循环仅以current.childCount == 1作为继续条件，没有考虑当前节点是否是某个单词的结束（eow == true）。虽然在单测试用例的main函数中运行{"a"}能得到正确结果，但这种逻辑会导致其他场景出错（比如输入{"app","apple"}时，错误返回"apple"而非"app"），同时在多测试用例环境下，静态状态污染会直接导致{"a"}的测试失败。

修复后的代码 #

class Solution {
    static class Node {
        Node[] children;
        int childCount;
        boolean eow;

        Node(){
            children = new Node[26];
            for (int i = 0; i < 26; i++){
                children[i] = null;
            }
            eow = false;
            childCount = 0;
        }
    }

    private Node root;

    public Solution() {
        root = new Node();
    }

    private void insertNode(String str){
        Node current = root;
        for (int i = 0; i < str.length(); i++){
            int index = str.charAt(i)-'a';
            if (current.children[index] == null){
                current.children[index] = new Node();
                current.childCount++;
            }
            if (i == str.length()-1){
                current.children[index].eow = true;
            }
            current = current.children[index];
        }
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (String s : strs) {
            if (s.isEmpty()) return "";
        }

        Solution trie = new Solution();
        for (String s : strs) {
            trie.insertNode(s);
        }

        Node current = trie.root;
        StringBuilder prefix = new StringBuilder();

        while (current.childCount == 1 && !current.eow) {
            for (int i =0; i < 26; i++) {
                if (current.children[i] != null){
                    prefix.append((char)(i+'a'));
                    current = current.children[i];
                    break;
                }
            }
        }

        return prefix.toString();
    }
}

关键修复点 #

• 将root改为非静态成员，每次调用longestCommonPrefix时创建新的Trie实例，确保每个测试用例的Trie树独立，彻底解决状态污染问题。
• 循环条件加入!current.eow判断，当遍历到某个单词的结束节点时停止，保证公共前缀不会超过最短单词的长度。
• 使用StringBuilder替代字符串拼接，提升性能。
• 增加边界情况处理，覆盖空数组、包含空字符串的场景，符合题目要求。

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