Code Implementation

class WordFilter:
    def __init__(self, words):
        self.lookup = {}
        for index, word in enumerate(words):
            length = len(word)
            for prefix_len in range(length + 1):
                prefix = word[:prefix_len]
                for suffix_len in range(length + 1):
                    suffix = word[length - suffix_len:]
                    self.lookup[(prefix, suffix)] = index

    def f(self, prefix, suffix):
        return self.lookup.get((prefix, suffix), -1)
      

class WordFilter {
public:
    unordered_map<string, int> lookup;
    WordFilter(vector<string>& words) {
        for (int index = 0; index < words.size(); ++index) {
            string& word = words[index];
            int n = word.size();
            for (int p = 0; p <= n; ++p) {
                string prefix = word.substr(0, p);
                for (int s = 0; s <= n; ++s) {
                    string suffix = word.substr(n - s, s);
                    lookup[prefix + "#" + suffix] = index;
                }
            }
        }
    }
    
    int f(string prefix, string suffix) {
        string key = prefix + "#" + suffix;
        return lookup.count(key) ? lookup[key] : -1;
    }
};
      

class WordFilter {
    private Map<String, Integer> lookup = new HashMap<>();
    public WordFilter(String[] words) {
        for (int index = 0; index < words.length; index++) {
            String word = words[index];
            int n = word.length();
            for (int p = 0; p <= n; p++) {
                String prefix = word.substring(0, p);
                for (int s = 0; s <= n; s++) {
                    String suffix = word.substring(n - s, n);
                    lookup.put(prefix + "#" + suffix, index);
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        String key = prefix + "#" + suffix;
        return lookup.getOrDefault(key, -1);
    }
}
      

class WordFilter {
    constructor(words) {
        this.lookup = new Map();
        for (let index = 0; index < words.length; ++index) {
            let word = words[index];
            let n = word.length;
            for (let p = 0; p <= n; ++p) {
                let prefix = word.slice(0, p);
                for (let s = 0; s <= n; ++s) {
                    let suffix = word.slice(n - s);
                    this.lookup.set(prefix + '#' + suffix, index);
                }
            }
        }
    }

    f(prefix, suffix) {
        let key = prefix + '#' + suffix;
        return this.lookup.has(key) ? this.lookup.get(key) : -1;
    }
}
      

Problem Description

You are given a list of words. Implement a class WordFilter that supports efficient retrieval of the highest index of a word that matches a given prefix and suffix.

• The constructor WordFilter(words) receives an array of strings words.
• The method f(prefix, suffix) returns the index of the word in words that has the given prefix and suffix, and if there are multiple valid answers, returns the largest index. If no word matches, return -1.

Key constraints:

• There is always one valid solution for each query if a match exists.
• Each call to f must be efficient, even for many queries.
• Prefixes and suffixes can be empty strings.
• Words may be repeated.

Thought Process

At first glance, for every query f(prefix, suffix), we might consider scanning through the words array and checking each word for a matching prefix and suffix. However, this brute-force approach is slow, especially if there are many queries or the word list is large.

To optimize, we need a way to quickly find the highest index of a word matching both prefix and suffix. This suggests pre-processing the words to build a fast lookup structure. The challenge is efficiently indexing all possible prefix and suffix combinations.

A naive approach would use two tries (one for prefixes, one for suffixes) and find the intersection, but that can be complex and slow for large datasets. Instead, we can precompute and store all (prefix, suffix) pairs for each word, mapping them to the word's index. This allows O(1) query time.

Solution Approach

We use a hash map (dictionary) to store every possible combination of prefix and suffix for each word, mapping each pair to the highest index where it occurs. Here's how we do it:

1. For each word in the input list, generate all possible prefixes (including the empty prefix) and all possible suffixes (including the empty suffix).
2. For every (prefix, suffix) pair, store the current word's index in the hash map. If the same pair appears for multiple words, the map will store the highest index (since later indices overwrite earlier ones).
3. To answer a query f(prefix, suffix), simply look up the pair in the hash map. If found, return the stored index; otherwise, return -1.

This method trades extra memory for very fast query times.

• Why a hash map? Because hash maps offer O(1) average lookup time, making queries extremely fast.
• Why store all combinations? So we don't have to search or build tries at query time; everything is precomputed.
• Why overwrite with higher indices? The problem asks for the largest index among matches.

Example Walkthrough

Suppose words = ["apple", "apply", "ape"].

Let's process f("ap", "e"):

• For each word, check if it starts with "ap" and ends with "e".
• "apple" matches (index 0), "apply" does not, "ape" matches (index 2).
• Among matches, the largest index is 2 ("ape").

With our pre-processing, when building the hash map, both ("ap", "e") will map to index 2, since "ape" is processed after "apple".

Querying f("ap", "e") returns 2.

For f("app", "le"), only "apple" matches, so answer is 0.

For f("a", "ly"), only "apply" matches, so answer is 1.

For f("b", "e"), no word matches, so answer is -1.

Time and Space Complexity

• Brute-force approach:
  • Each query scans all words (O(N)), checking prefix and suffix (O(L) for each word), for O(N * L) per query, where N is the number of words and L is max word length.
• Optimized approach (hash map):
  • Construction time: For each word, we generate (L+1) prefixes and (L+1) suffixes, so O(N * L²) total.
  • Space: We store O(N * L²) entries in the hash map.
  • Query time: O(1) per query, since it's just a hash map lookup.

The trade-off is increased memory usage for much faster queries.

Summary

The key insight is to precompute all possible (prefix, suffix) pairs for every word and store them in a hash map with the highest index. This allows each query to be answered in constant time, at the cost of higher memory usage. The solution is elegant because it leverages the power of hash maps to turn a potentially slow problem into a very efficient one, especially when many queries are required.