Course4all

Prefix and Suffix Search (Optimized Query)

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

Prefix and Suffix Search (Optimized Query)

The same as Prefix and Suffix Search, but focused on extreme query performance.
Hard
Approach 1

Level I: Brute Force Search

Intuition

For each query, iterate through the entire dictionary. For each word, check if it starts with the prefix and ends with the suffix. Return the maximum index found. O(N * L) per query.
⏱ O(N * L) per query.💾 O(1)
java
// O(N*L) search
Approach 2

Level III: Precomputed HashMap of Pairs

Intuition

For cases where memory is available but query speed is critical, precompute all possible (prefix, suffix) pairs for every word. Use a HashMap to store prefix + " " + suffix as the key and the max index as the value.
⏱ Query: O(1). Initialization: O(N * L^2).💾 O(N * L^2).
java
class WordFilter {
    Map<String, Integer> map = new HashMap<>();
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            for (int p = 0; p <= words[i].length(); p++) {
                String pre = words[i].substring(0, p);
                for (int s = 0; s <= words[i].length(); s++) {
                    map.put(pre + " " + words[i].substring(s), i);
                }
            }
        }
    }
    public int f(String prefix, String suffix) {
        return map.getOrDefault(prefix + " " + suffix, -1);
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionLongest Word in Dictionary through Deleting
Next Question →Number of Islands