Leetcode: Prefix and Suffix Search

This question is asked at Amazon and Facebook and is as follows: 

Design a special dictionary which has some words and allows you to search the words in it by a prefix and a suffix. 

Implement the WordFilter class: 

WordFilter(string[] words) initializes the object with words in the dictionary.

f(string prefix, string suffix) returns the index of the word in the dictionary which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no word in the dictionary, return -1. 

Here's an example:

Input: ["WordFilter", "f"]

[[["apple"]], ["a", "e"]]

Output: [null, 0] 

Explanation: 

WordFilter wordFilter = new WordFilter(["apple"]);

wordFilter.f("a", "e") //return 0, because the word at index 0 has the prefix "a" and the suffix "e".

 For this question, we use a trie. In fact, we use 2 tries. 

We use 2 tries. One trie is so separately find all the words that match the prefix, plus all of the words that match the suffix, then try to find the highest weight element in the intersection of these sets. Here's the implementation: 

class WordFilter {

    class TrieNode {

        TrieNode[] children;

        Set<Integer> weight;

        public TrieNode() {

            children = new TrieNode[26];

            weight = new HashSet();

        }

    }

    TrieNode trie1, trie2; 

    public WordFilter(String[] words) {

        trie1 = new TrieNode();

        trie2 = new TrieNode();

        int wt = 0;

        for(String word : words) {

            char[] ca = word.toCharArray();

            TrieNode cur = trie1;

            cur.weight.add(wt);

            for(char letter : ca) {

                if(cur.children[letter - 'a'] == null) {

                    cur.children[letter - 'a'] = new TrieNode();

                }

                cur = cur.children[letter - 'a'];

                cur.weight.add(wt);

            }

        wt++;

        }

    }

    public int f(String prefix, String suffix) {

        TrieNode curl = trie1, cur2 = trie2;

        for(char letter : prefix.toCharArray()) {

            if(curl.children[letter - 'a'] == null) return -1; 

            curl = curl.children[letter - 'a'];

        }

        char[] ca = suffix.toCharArray();

        for (int j = ca.length - 1; j >= 0; --j) {

            char letter = ca[j];

            if (cur2.children[letter - 'a'] == null) return -1;

            cur2 = cur2.children[letter - 'a'];

        }    

        int ans = -1;

        for(int w1: curl.weight) {

            if(w1 > ans && cur2.weight.contains(w1)) ans = w1;

        }

        return ans;

    }

}

However, this returns an overflow error, so we should in return have more of a trie structure. 

Let's take "apple" as an example, we will insert add  "apple{apple", "pple{apple", "ple{apple", "le{apple", "e{apple", "{apple" into this particular Trie. It will be of size 27, as "{" counts as one of the TrieNodes in the subset. 

If the query is app(prefix) and le(suffix) we can find the verse by querying the Trie for "le { app". We use "{" because in the ASCII table we need to create the TrieNode[27] instead of 26.   

//trie data structure 

class TrieNode {

    TrieNode[] children;

    int weight;

    public TrieNode() {

        children = new TrieNode[27];

        weight = 0;

    }

public class WordFilter {

    TrieNode root;

    //find the root

    public WordFilter(String[] words) {

        root = new TrieNode(); 

        //iterate through all the words

        for(int weight = 0; weight < words.length; weight++) {

            String word = words[weight] + "{";

            //add prefix and suffix integer

            for(int j = i; j < 2 * word.length() - 1; j++) {

                int k = word.charAt(j % wordLength()) - 'a';

                //add a Trie node on the kth integer

                if(curr.children[k] == null) curr.children[k] = new TrieNode;

                cur = cur.children[k];

                cur.weight = weight; 

            }

        }

    }

} 

public int f(String prefix, String suffix) {

    TrieNode cur = root;

    //find the suffix and the prefix and attempt to see the children of the last character? 

    //iterate to the last character

    for(char c: (suffix + '{' + prefix).toCharArray()) {

        if(cur.children[c - 'a'] == null) {

            return -1;

        }

        cur = cur.children[c - 'a'];

    }

    //return the weight of the specified character. 

    return cur.weight; 

}