Course4all
Join us on telegram
Home/dsa/Trie/Prefix and Suffix Search (Optimized Query)

Prefix and Suffix Search (Optimized Query)

Master this topic with zero to advance depth.

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);
    }
}
← Previous QuestionLongest Word in Dictionary through Deleting
Next Question →Number of Islands