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

Question

I am trying to solve the problem, essentially we need to find all words from dictionary which have the given prefix in lexicographic order.

I am using Trie data structure for the task but my solution just times out on the judge , what can be a more efficient/faster way to solve this problem?

My current implementation is

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

            }
        }
    }

}

The function Search returns the sorted list of all words that share the given prefix.

Also is there a better data structure i could use for this?

Answer 1

Tries are great at finding a substring of another string. However, you are searching for words in a dictionary - substring matching is not really necessary. Also, once you find the first word with the prefix, the next word, if it exists, will be right next to it. No complex search required!

Tries also carry a lot of overhead from being built out of nodes, which then need to be referenced with pointers (= extra space requirements). Pointers are slow. In C++, iterating linked lists can be 20x slower than iterating arrays, unless the nodes are all nicely ordered.

This problem can, very probably, be solved via

• reading all words into an ArrayList of String: O(n), with n = words
• sorting the ArrayList: O(n log n)
• and for each prefix query,
  • using binary search to find the 1st match for the prefix: O(log n), and it is already implemented in the standard library
  • returning consecutive elements that match until matches are exhausted: O(m), m = number of matches

This is faster than Tries on theoretical complexity, and and a lot faster due to memory layout - messing with pointers, when you don't need to do so, is expensive.