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

Question

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

我正在使用 Trie 数据结构来完成任务，但我的解决方案在判断时超时，还有什么方法可以解决这个问题？efficient/faster

我目前的实现是

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);

            }
        }
    }

}

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

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

Answer 1

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

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

这个问题很可能可以通过

解决

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

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

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

What can be a faster implementation of trie for the following use case?

java

string

algorithm

trie

data-structures