java - 对于以下用例，什么可以更快地实现 trie？

Question

我正在尝试解决 problem ，本质上我们需要从字典中找到所有具有给定前缀的字典顺序的单词。

我正在为任务使用 Trie 数据结构，但我的解决方案在判断时超时，有什么方法可以更有效/更快地解决这个问题？

我目前的实现是

class trie{
    node root=new node();
    class node{
        node child[]=new node[26];
        boolean is_leaf=false;
    }

    public void add(char c[])
    {
        node root=this.root;
        int pos=0,c1=0;
        while(pos<c.length)
        {
            c1=c[pos]-'a';
            if(root.child[c1]==null)
            {
                root.child[c1]=new node();
            }
            root=root.child[c1];
            pos++;
        }
        root.is_leaf=true;
    }
    public ArrayList<String> search(String s)
    {
        char c[]=s.toCharArray();
        node root=this.root;
        int pos=0,c1=0;
        while(pos<c.length)
        {
            c1=c[pos]-'a';
            if(root.child[c1]==null)
            {
                root.child[c1]=new node();
            }
            root=root.child[c1];
            pos++;
        }
        ArrayList<String> ans=new ArrayList<>();
        build_recursive(root,s,new StringBuilder(),ans);
        return ans;

    }
    public void build_recursive(node root,String prefix,StringBuilder cur, ArrayList<String> ans)
    {
        if(root.is_leaf&&cur.length()!=0)
        {
            String s=prefix+cur.toString();
            ans.add(s);
        }

        for(int i=0;i<26;i++)
        {
            if(root.child[i]!=null)
            {
                char c=(char) (i+'a');
                cur.append(c);
                build_recursive(root.child[i], prefix, cur, ans);
                cur.deleteCharAt(cur.length()-1);

            }
        }
    }

}

搜索函数返回共享给定前缀的所有单词的排序列表。

我还可以使用更好的数据结构吗？

Answer 1

尝试非常适合寻找另一个字符串的子字符串。但是，您正在字典中搜索单词 - 子字符串匹配并不是真正必要的。此外，一旦找到带前缀的第一个单词，下一个单词(如果存在)将紧挨着它。无需复杂的搜索!

Tries 还带有很多从节点构建的开销，然后需要用指针引用它们(= 额外的空间要求)。指针很慢。在 C++ 中，迭代链表 can be 20x slower而不是迭代数组，除非节点都井井有条。

这个问题很可能可以通过以下方式解决

• 将所有单词读入字符串的 ArrayList:O(n)，其中 n = 单词
• 对 ArrayList 进行排序:O(n log n)
• 对于每个前缀查询，
  • 使用binary search找到前缀的第一个匹配项:O(log n)，它已经在标准库中实现
  • 返回匹配的连续元素，直到匹配耗尽:O(m)，m = 匹配数

这在理论上的复杂性上比 Tries 更快，而且由于内存布局要快得多 - 在不需要时乱用指针是很昂贵的。