Prefix and Suffix Search
Problem
Implement WordFilter so that f(prefix, suffix) returns the largest index i such that words[i] starts with prefix and ends with suffix, or -1 if none exists.
words=["apple"]; f("a","e")0class WordFilter:
def __init__(self, words):
self.trie = {}
for i, w in enumerate(words):
for s in range(len(w) + 1):
key = w[s:] + '#' + w
node = self.trie
for ch in key:
node = node.setdefault(ch, {})
node['$'] = i
def f(self, prefix, suffix):
key = suffix + '#' + prefix
node = self.trie
for ch in key:
if ch not in node: return -1
node = node[ch]
return node.get('$', -1)class WordFilter {
constructor(words) {
this.trie = {};
for (let i = 0; i < words.length; i++) {
const w = words[i];
for (let s = 0; s <= w.length; s++) {
const key = w.slice(s) + '#' + w;
let node = this.trie;
for (const ch of key) {
if (!node[ch]) node[ch] = {};
node = node[ch];
node.$ = i;
}
}
}
}
f(prefix, suffix) {
const key = suffix + '#' + prefix;
let node = this.trie;
for (const ch of key) {
if (!node[ch]) return -1;
node = node[ch];
}
return node.$ ?? -1;
}
}class WordFilter {
static class Node { Map<Character, Node> next = new HashMap<>(); int idx = -1; }
Node root = new Node();
public WordFilter(String[] words) {
for (int i = 0; i < words.length; i++) {
String w = words[i];
for (int s = 0; s <= w.length(); s++) {
String key = w.substring(s) + "#" + w;
Node node = root;
for (char ch : key.toCharArray()) {
node = node.next.computeIfAbsent(ch, k -> new Node());
node.idx = i;
}
}
}
}
public int f(String prefix, String suffix) {
String key = suffix + "#" + prefix;
Node node = root;
for (char ch : key.toCharArray()) {
node = node.next.get(ch);
if (node == null) return -1;
}
return node.idx;
}
}class WordFilter {
struct Node { unordered_map<char, Node*> next; int idx = -1; };
Node* root = new Node();
public:
WordFilter(vector<string>& words) {
for (int i = 0; i < (int)words.size(); i++) {
const string& w = words[i];
for (int s = 0; s <= (int)w.size(); s++) {
string key = w.substr(s) + "#" + w;
Node* node = root;
for (char ch : key) {
if (!node->next.count(ch)) node->next[ch] = new Node();
node = node->next[ch];
node->idx = i;
}
}
}
}
int f(string prefix, string suffix) {
string key = suffix + "#" + prefix;
Node* node = root;
for (char ch : key) {
if (!node->next.count(ch)) return -1;
node = node->next[ch];
}
return node->idx;
}
};Explanation
We need the largest index of a word that matches both a prefix and a suffix. The clever trick is to combine both conditions into a single trie key by storing, for each word, every string of the form suffix + '#' + word.
During construction, for each word we take all of its suffixes (including the whole word and the empty suffix) and insert suffix#word into one big trie. At every node along the way we overwrite the stored index with the current word's index i. Because words are processed in order, later (larger) indices naturally replace earlier ones — giving us the largest matching index for free.
A query f(prefix, suffix) just builds the key suffix + '#' + prefix and walks it through the trie. If the walk completes, the index stored at the final node is the answer; if any character is missing, we return -1.
Example: words ["apple"], query f("a", "e"). The key "e#a" matches a path that was created from the suffix e of apple, and the stored index 0 is returned.
Building inserts about L suffix-keys of length L per word (the N·L² cost), but each query is just one fast walk of length prefix + suffix.