Prefix and Suffix Search

Problem

Design a special dictionary with some words that searchs the words in it by a prefix and a suffix.

Implement the WordFilter class:

WordFilter(string[] words) Initializes the object with the 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 such word in the dictionary, return -1.

Example 1:

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 prefix = "a" and suffix = 'e".

Constraints:

1 <= words.length <= 15000
1 <= words[i].length <= 10
1 <= prefix.length, suffix.length <= 10
words[i], prefix and suffix consist of lower-case English letters only.
At most 15000 calls will be made to the function f.

Solution

class WordFilter {
    constructor(words) {
        this.trie = new Trie();

        for (let i = 0; i < words.length; i++) {
            const w = words[i];
            let word = "#" + w;
            this.trie.insert(word);

            // go through all possible suffix
            for (let j = w.length - 1; j >= 0; j--) {
                const c = w[j];
                word = c + word;
                this.trie.insert(word, i);
            }
        }
    }

    f(prefix, suffix) {
        return this.trie.startsWith(`${suffix}#${prefix}`);
    }
}

class Node {
    constructor() {
        this.end = false;
        this.index = -1; // max index
        this.children = {};
    }
}

class Trie {
    constructor() {
        this.root = new Node();
    }

    insert(word, index) {
        let r = this.root;
        for (const c of word) {
            if (!(c in r.children)) {
                r.children[c] = new Node();
            }
            r = r.children[c];
            r.index = Math.max(index, r.index);
        }
        r.end = true;
    }

    startsWith(prefix) {
        let r = this.root;
        for (const c of prefix) {
            if (!(c in r.children)) {
                return -1;
            }
            r = r.children[c];
        }
        return r.index;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * var obj = new WordFilter(words)
 * var param_1 = obj.f(prefix,suffix)
 */

We will use a trie to implement our solution. Consider the word 'apple'. For each suffix of the word, we could insert that suffix, followed by '#', followed by the word, all into the trie.

For example, we will insert '#apple', 'e#apple', 'le#apple', 'ple#apple', 'pple#apple', 'apple#apple' into the trie. Then for a query like prefix = "ap", suffix = "le", we can find it by querying our trie for words that starts with le#ap.

Furthermore, in order to return the largest index when there is more then one word, we modify our trie so each node has an additional field index. This field will contain the maximum index of each word in words that uses the current node.

Note that another solution is to use a hashmap to store all possible suffix and prefix combinations of each word in words. Using this method, f would have O(1) runtime, but would require more space as a result.

Problem​

Solution​

Problem

Solution