Course4all
Join us on telegram
Home/dsa/Trie/Prefix and Suffix Search

Prefix and Suffix Search

Master this topic with zero to advance depth.

Prefix and Suffix Search

Design a data structure that allows searching for a word with a given prefix AND a given suffix. If there are multiple valid words, return the largest index.

Visual Representation

Words: ["apple"] Suffix#Prefix construction: "e#apple", "le#apple", "ple#apple", ... Insert these into a Trie. Query: prefix="ap", suffix="le" Search Trie for "le#ap". Found node stores max index: 0.
Hard

Examples

Input: ["WordFilter", "f"] [[["apple"]], ["a", "e"]]
Output: [null, 0]
Approach 1

Level I: HashMap (All Combinations)

Intuition

Pre-calculate all potential prefix + '#' + suffix combinations for every word and store them in a HashMap with their index. Query is O(1). Inefficient space but simple.

⏱ Pre: O(N * L^2), Query: O(1).💾 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++) {
                for (int s = 0; s <= words[i].length(); s++) {
                    map.put(words[i].substring(0, p) + "#" + words[i].substring(words[i].length()-s), i);
                }
            }
        }
    }
    public int f(String prefix, String suffix) {
        return map.getOrDefault(prefix + "#" + suffix, -1);
    }
}
Approach 2

Level III: Wrapped Trie ({suffix}#{prefix})

Intuition

To handle both prefix and suffix in a single search, we can insert multiple variations of each word into the Trie. For a word like 'apple', insert: '#apple', 'e#apple', 'le#apple', 'ple#apple', 'pple#apple', 'apple#apple'. A query with prefix 'a' and suffix 'le' becomes a prefix search for 'le#a' in this special Trie.

⏱ Initialization: O(N * L^2), Search: O(L).💾 O(N * L^2).
java
import java.util.*;
class WordFilter {
    class Node { Node[] children = new Node[27]; int weight; }
    Node root = new Node();
    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String w = "{" + words[i];
            insert(w, i);
            for (int j = words[i].length() - 1; j >= 0; j--) {
                w = words[i].charAt(j) + w;
                insert(w, i);
            }
        }
    }
    private void insert(String s, int weight) {
        Node curr = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) curr.children[idx] = new Node();
            curr = curr.children[idx]; curr.weight = weight;
        }
    }
    public int f(String prefix, String suffix) {
        Node curr = root;
        for (char c : (suffix + "{" + prefix).toCharArray()) {
            if (curr.children[c - 'a'] == null) return -1;
            curr = curr.children[c - 'a'];
        }
        return curr.weight;
    }
}
← Previous QuestionCamelcase Matching
Next Question →Word Ladder II