Skip to main content
CodePeet

Prefix and Suffix Search

Try it yourself
HardProblemExternal link

Description

Design a dictionary that can find a word by how it begins and how it ends at the same time.

Implement the WordFilter class:

  • WordFilter(words) — builds the dictionary from the list words. A word's position in the list is its index, starting from 0.
  • int f(pref, suff) — returns the index of a word that starts with pref and ends with suff. If several words qualify, return the largest of their indexes. If no word qualifies, return -1.

A few details decide the answer:

  • Both tests apply to the same word, and the two parts may overlap inside it: "stone" starts with "sto" and ends with "tone", and the letters "to" count for both.
  • Either part may be the whole word: "kit" starts with "kit" and ends with "t".
  • A word can appear in the list more than once. Each copy has its own index, so the later copy is the one to return.

Examples

Example 1

Input:

["WordFilter", "f", "f", "f", "f"]
[[["stone", "stove", "store", "shore"]], ["st", "e"], ["s", "ore"], ["sto", "tone"], ["sh", "ove"]]

Output: [null, 2, 3, 0, -1]

Explanation: The words are "stone" (index 0), "stove" (1), "store" (2) and "shore" (3).

  • f("st", "e") → 2. Three words begin with "st" and end with "e": stone, stove and store. The largest index among them is 2. ("shore" ends with "e" but begins with "sh".)
  • f("s", "ore") → 3. Both "store" and "shore" end with "ore", and both begin with "s". The larger index is 3.
  • f("sto", "tone") → 0. Only "stone" fits. Its prefix "sto" and suffix "tone" overlap on the letters "to", which is allowed.
  • f("sh", "ove") → -1. "shore" begins with "sh" and "stove" ends with "ove", but no single word does both.

Example 2

Input:

["WordFilter", "f", "f", "f"]
[[["to", "two"]], ["t", "o"], ["to", "o"], ["to", "wo"]]

Output: [null, 1, 0, -1]

Explanation:

  • f("t", "o") → 1. "to" (index 0) and "two" (index 1) both begin with "t" and end with "o". The larger index wins.
  • f("to", "o") → 0. Only "to" begins with "to"; "two" begins with "tw".
  • f("to", "wo") → -1. Only "two" ends with "wo", and it does not begin with "to".

Example 3

Input:

["WordFilter", "f", "f", "f"]
[[["kite", "kit", "kite"]], ["kit", "e"], ["kit", "t"], ["kites", "s"]]

Output: [null, 2, 1, -1]

Explanation:

  • f("kit", "e") → 2. "kite" appears twice, at indexes 0 and 2, and both copies fit. The later copy's index is returned.
  • f("kit", "t") → 1. The prefix can be the entire word: "kit" begins with "kit" and ends with "t". ("kite" ends with "e".)
  • f("kites", "s") → -1. The prefix is longer than every word, so nothing can begin with it.

Constraints

  • 1 ≤ words.length ≤ 10^4
  • 1 ≤ words[i].length ≤ 7
  • 1 ≤ pref.length, suff.length ≤ 7
  • words[i], pref and suff consist of lowercase English letters only.
  • At most 10^4 calls will be made to f.

Editorial

Brute Force

Intuition

The simplest dictionary is the list itself. Keep words exactly as given, and answer each query by checking the words one at a time.

Checking a word is two small tests: do its first len(pref) letters equal pref, and do its last len(suff) letters equal suff? A word shorter than pref or suff fails at once.

The only real decision is the order of the scan. The query wants the largest index, so start at the last word and walk toward the first. The first word that passes both tests has the largest index of all the words that fit, and the scan can stop right there. If it runs off the front of the list without a match, the answer is -1.

Think of a stack of index cards, newest on top. To find the newest card that fits, you flip from the top and stop at the first one that does. You never have to look at the older cards below it.

Step-by-Step Explanation

We trace two queries on Example 1, words = ["stone", "stove", "store", "shore"]. The first finds a match quickly; the second reads the whole list.

Step 1: Query f("st", "e"). Start at the last index, 3, because the first match found from the back has the largest index.

Step 2: Index 3, "shore": it begins with "sh", not "st" — rejected without checking the suffix. (It does end with "e", but one test is not enough.)

Step 3: Index 2, "store": it begins with "st" — the prefix test passes.

Step 4: "store" also ends with "e" — both tests pass.

Step 5: Return 2. "stone" and "stove" would also fit, but scanning from the back means we stop before reaching them.

Step 6: Query f("sh", "ove"). Start at the last index, 3, because the first match found from the back has the largest index.

Step 7: Index 3, "shore": it begins with "sh" — the prefix test passes.

Step 8: "shore" ends with "ore", not "ove" — rejected.

Step 9: Index 2, "store": it begins with "st", not "sh" — rejected without checking the suffix.

Step 10: Index 1, "stove": it begins with "st", not "sh" — rejected without checking the suffix. (It does end with "ove", but one test is not enough.)

Step 11: Index 0, "stone": it begins with "st", not "sh" — rejected without checking the suffix.

Step 12: The scan ran off the front of the list, so return -1. Every word was read to answer a single query.

Brute Force — Scanning From the Back — Each query walks the list from the last word to the first and stops at the first word that begins with pref and ends with suff.

Algorithm

  1. Constructor: keep the list words.
  2. f(pref, suff):
    • For i from the last index down to 0:
      • If words[i] starts with pref and ends with suff, return i.
    • Return -1.

Code

#include <string>
#include <vector>
using namespace std;

class WordFilter {
    vector<string> words;

    static bool startsWith(const string& word, const string& pref) {
        return word.size() >= pref.size() && word.compare(0, pref.size(), pref) == 0;
    }

    static bool endsWith(const string& word, const string& suff) {
        return word.size() >= suff.size() &&
               word.compare(word.size() - suff.size(), suff.size(), suff) == 0;
    }

public:
    WordFilter(vector<string>& words) : words(words) {}

    int f(string pref, string suff) {
        // Scan from the back: the first word that fits has the largest index.
        for (int i = (int)words.size() - 1; i >= 0; i--) {
            if (startsWith(words[i], pref) && endsWith(words[i], suff)) return i;
        }
        return -1;
    }
};
class WordFilter:
    def __init__(self, words: list[str]):
        self.words = words

    def f(self, pref: str, suff: str) -> int:
        # Scan from the back: the first word that fits has the largest index.
        for i in range(len(self.words) - 1, -1, -1):
            word = self.words[i]
            if word.startswith(pref) and word.endswith(suff):
                return i
        return -1
class WordFilter {
    private final String[] words;

    public WordFilter(String[] words) {
        this.words = words;
    }

    public int f(String pref, String suff) {
        // Scan from the back: the first word that fits has the largest index.
        for (int i = words.length - 1; i >= 0; i--) {
            if (words[i].startsWith(pref) && words[i].endsWith(suff)) return i;
        }
        return -1;
    }
}

Complexity Analysis

Let N be the number of words, p = len(pref) and s = len(suff).

Time Complexity:

  • Constructor: O(1) in Python and Java, which keep a reference to the list. The C++ version copies it, which is O(N · L) for words of length up to L.
  • f: O(N · (p + s)). A query may check every word, and each check compares up to p + s letters. Across Q queries that is O(Q · N · (p + s)).

Space Complexity: O(N · L) for the stored words, and nothing else. No extra structure is built.

Why This Approach Is Not Efficient

Every query starts from zero. The dictionary never changes between calls to f, yet each call reads the list again from the back.

The worst case is easy to build: 10,000 words that all begin with "a", queried 10,000 times with f("a", "z"). Every word passes the prefix test and fails the suffix test, so each query reads all 10,000 words. That is 10^4 × 10^4 = 10^8 word checks. Measured on exactly that input, the scan takes about 3.7 seconds in Python (about 0.5 s in C++). The trie approach at the end of this editorial answers the same input in 0.3 s in Python.

The constructor runs once and f runs up to 10,000 times. So the right trade is to do more work in the constructor if it makes each query cheaper.

A tempting half-fix is to index the words by prefix and, separately, by suffix, then combine the two lists at query time. It breaks on common pairs. With pref = "s" and suff = "e", thousands of words can match each half on its own, and merging two long lists costs about as much as the scan. The prefix and the suffix have to be indexed together, as a pair.

How many pairs can one word answer? A word of length L has L non-empty prefixes and L non-empty suffixes, so at most L × L pairs. Here L ≤ 7, so at most 49 pairs per word. That is few enough to write every one down in advance.

Better Approach - Hash Map of Every (Suffix, Prefix) Pair

Intuition

Every query f(pref, suff) asks about exactly one (suffix, prefix) pair. So in the constructor, list every pair each word can answer and store it in a hash map from the pair to the word's index. A query then becomes a single lookup.

Two details make this work:

  • One key per pair. A hash map needs a single key, so glue the two parts together: the suffix, then the separator {, then the prefix. For the word "two" with suffix "wo" and prefix "t", the key is "wo{t". The separator must be a character that never appears in a word, and { qualifies because words contain only lowercase letters. The separator is not optional. Without it, suffix "ab" + prefix "c" and suffix "a" + prefix "bc" would both become "abc", and two different pairs would share one key.
  • Largest index for free. Add words in index order and let a later word overwrite an earlier one. When construction finishes, each key holds the index of the last word that produced it, which is the largest.

Putting the suffix first, and choosing { in particular, makes no difference to a hash map. Both choices pay off in the next approach.

Step-by-Step Explanation

We trace Example 2, words = ["to", "two"]. Construction writes one key per (suffix, prefix) pair; then we answer the three queries.

Step 1: Start with an empty map.

Step 2: Word 0 "to", suffix "to", prefix "t" → store "to{t" = 0.

Step 3: Word 0 "to", suffix "to", prefix "to" → store "to{to" = 0.

Step 4: Word 0 "to", suffix "o", prefix "t" → store "o{t" = 0.

Step 5: Word 0 "to", suffix "o", prefix "to" → store "o{to" = 0.

Step 6: Word 1 "two", suffix "two", prefix "t" → store "two{t" = 1.

Step 7: Word 1 "two", suffix "two", prefix "tw" → store "two{tw" = 1.

Step 8: Word 1 "two", suffix "two", prefix "two" → store "two{two" = 1.

Step 9: Word 1 "two", suffix "wo", prefix "t" → store "wo{t" = 1.

Step 10: Word 1 "two", suffix "wo", prefix "tw" → store "wo{tw" = 1.

Step 11: Word 1 "two", suffix "wo", prefix "two" → store "wo{two" = 1.

Step 12: Word 1 "two", suffix "o", prefix "t" → "o{t" already exists with value 0. Overwrite it with 1 — the later word has the larger index.

Step 13: Word 1 "two", suffix "o", prefix "tw" → store "o{tw" = 1.

Step 14: Word 1 "two", suffix "o", prefix "two" → store "o{two" = 1.

Step 15: f("t", "o"): look up "o{t" → found, value 1. Return 1.

Step 16: f("to", "o"): look up "o{to" → found, value 0. Return 0.

Step 17: f("to", "wo"): look up "wo{to" → not in the map. Return -1.

Hash Map — Every (Suffix, Prefix) Pair as One Key — Construction writes one key per suffix and prefix of every word, letting later words overwrite earlier ones; each query is then a single lookup.

Algorithm

  1. Constructor: create an empty map best.
    • For each index, word in order:
      • For every suffix of word (from the whole word down to its last letter):
        • For every prefix of word:
          • Set best[suffix + "{" + prefix] = index (overwriting any earlier value).
  2. f(pref, suff): return best[suff + "{" + pref] if the key exists, otherwise -1.

Code

#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class WordFilter {
    // "suffix{prefix" -> index. Words are added in order, so a later word
    // overwrites an earlier one and each key ends up with the largest index.
    unordered_map<string, int> best;

public:
    WordFilter(vector<string>& words) {
        for (int index = 0; index < (int)words.size(); index++) {
            const string& word = words[index];
            int n = word.size();
            for (int start = 0; start < n; start++) {
                string suffix = word.substr(start);
                for (int len = 1; len <= n; len++) {
                    best[suffix + '{' + word.substr(0, len)] = index;
                }
            }
        }
    }

    int f(string pref, string suff) {
        auto it = best.find(suff + '{' + pref);
        return it == best.end() ? -1 : it->second;
    }
};
class WordFilter:
    def __init__(self, words: list[str]):
        # "suffix{prefix" -> index. Words are added in order, so a later word
        # overwrites an earlier one and each key ends up with the largest index.
        self.best = {}
        for index, word in enumerate(words):
            for start in range(len(word)):
                suffix = word[start:]
                for end in range(1, len(word) + 1):
                    self.best[suffix + '{' + word[:end]] = index

    def f(self, pref: str, suff: str) -> int:
        return self.best.get(suff + '{' + pref, -1)
import java.util.HashMap;
import java.util.Map;

class WordFilter {
    // "suffix{prefix" -> index. Words are added in order, so a later word
    // overwrites an earlier one and each key ends up with the largest index.
    private final Map<String, Integer> best = new HashMap<>();

    public WordFilter(String[] words) {
        for (int index = 0; index < words.length; index++) {
            String word = words[index];
            int n = word.length();
            for (int start = 0; start < n; start++) {
                String suffix = word.substring(start);
                for (int len = 1; len <= n; len++) {
                    best.put(suffix + "{" + word.substring(0, len), index);
                }
            }
        }
    }

    public int f(String pref, String suff) {
        return best.getOrDefault(suff + "{" + pref, -1);
    }
}

Complexity Analysis

Let N be the number of words and L their maximum length (at most 7).

Time Complexity:

  • Constructor: O(N · L³). Each word produces up to L × L keys, and building and hashing one key touches up to 2L + 1 characters. For N = 10^4 and L = 7 that is 490,000 keys holding about 4.4 million characters.
  • f: O(p + s). Building the key and hashing it touches p + s + 1 characters, and the lookup itself takes constant time on average.

Space Complexity: O(N · L³) characters across all the keys, in the worst case where no two words share a pair. At full size (10,000 random 7-letter words) the whole program peaked at about 74 MB in Python and 36 MB in C++.

Why This Approach Is Not Efficient

The queries are now as fast as they can get. A query has to read its own p + s letters no matter what, and a lookup does little more than that. What remains is the construction, and it does a lot of repeated copying.

Look at the three keys built for the word "two" with suffix "o": "o{t", "o{tw", "o{two". Each one copies "o{" again, then a longer piece of "two". They are not three unrelated strings. They are the beginnings of one string, "o{two". The same is true for every suffix: the L keys built for one suffix are exactly the beginnings of suffix + "{" + word.

So a 7-letter word writes 49 keys, 441 characters in total, when 7 strings of 84 characters in total would describe the same pairs. That only works with a structure that can answer "is my key the beginning of some stored string?". That structure is a trie. Using it cuts construction from O(N · L³) to O(N · L²).

Optimal Approach - Trie of "suffix{word" Strings

Intuition

For each word and each of its suffixes, store one string: suffix + { + the whole word. For "two", that is "two{two", "wo{two" and "o{two". Put all these strings into a trie: a tree whose edges are single characters, where every stored string is a path down from the root. Every beginning of every stored string is a node you can reach.

A query f(pref, suff) builds the same key the hash map used, suff + { + pref, and walks it down from the root. The key is a beginning of a stored string suffix + { + word in exactly one situation: the stored suffix equals suff, and the word starts with pref. The { makes the suffix part exact. The walk cannot stop partway through a suffix, or run past one, because it has to meet the { right after suff.

For the word "two" and its suffix "o", the hash map stores three separate keys, o{t, o{tw and o{two, while the trie stores one path o, {, t, w, o. The three keys are three stops along that one path, so one stored string answers every prefix of the word for that suffix.

Each node remembers one number: the index of the last word whose stored string passed through it. Words are inserted in index order, so that number is the largest index among all words that reach the node. When a query's walk ends at a node, that number is the answer. If an edge is missing partway through the walk, no word fits, and the answer is -1.

Now the two choices from the hash map approach pay off:

  • Why the suffix goes first. A trie matches beginnings of stored strings. The word's prefixes are already its beginnings, so the word can sit after the { and every prefix is covered at once. A suffix cannot be covered that way, so each suffix is written out in front, one stored string per suffix.
  • Why {. In character codes, { comes right after z. In an array of 27 child slots, '{' - 'a' is 26, the slot after z's 25, with no special case needed.

Step-by-Step Explanation

We trace Example 2 again, words = ["to", "two"]. Five strings are stored, then the three queries walk the trie.

Step 1: Start with an empty trie — just the root.

Step 2: Store "to{to" for word 0 "to", suffix "to": 5 new nodes, each remembering 0.

Step 3: Store "o{to" for word 0 "to", suffix "o": 4 new nodes, each remembering 0.

Step 4: Store "two{two" for word 1 "two", suffix "two": the node "t" already exists, so it now remembers 1 instead of 0; 6 new nodes remember 1.

Step 5: Store "wo{two" for word 1 "two", suffix "wo": 6 new nodes, each remembering 1.

Step 6: Store "o{two" for word 1 "two", suffix "o": the first 3 nodes, "o{t", already exist, so they now remember 1 instead of 0; 2 new nodes remember 1.

Step 7: f("t", "o") → key "o{t". Follow "o" from the root: it exists.

Step 8: Follow "{": it exists.

Step 9: Follow "t": the whole key is matched. The node remembers 1 (word 1 passed through it last), so return 1.

Step 10: f("to", "o") → key "o{to". Every edge exists; the last node lies only on "o{to", so it remembers 0. Return 0.

Step 11: f("to", "wo") → key "wo{to". The first four characters, "wo{t", exist.

Step 12: The next character, "o", has no edge — the only way on is "w". Return -1.

Trie of "suffix{word" Strings — Build, Then Walk — Five stored strings for "to" and "two" share their beginnings; each query walks suffix + "{" + prefix and reads the index the last node remembers.

Algorithm

Node: a set of children keyed by character (a–z and {), plus index, the index of the last word that passed through.

  1. Constructor:
    • For each index, word in order:
      • For each suffix of word:
        • Walk the string suffix + { + word from the root, creating missing nodes.
        • At every node on the walk, set node.index = index.
  2. f(pref, suff):
    • Walk the key suff + { + pref from the root.
    • If a character has no edge, return -1.
    • Otherwise return the index stored at the node where the walk ends.

Code

#include <string>
#include <vector>
using namespace std;

class WordFilter {
    struct TrieNode {
        TrieNode* next[27] = {};  // 'a'..'z', then '{', the character right after 'z'
        int index = -1;           // largest index of a word whose stored string passes here
    };
    TrieNode* root = new TrieNode();

public:
    WordFilter(vector<string>& words) {
        for (int index = 0; index < (int)words.size(); index++) {
            const string& word = words[index];
            for (int start = 0; start < (int)word.size(); start++) {
                string stored = word.substr(start) + '{' + word;
                TrieNode* node = root;
                for (char ch : stored) {
                    int slot = ch - 'a';
                    if (!node->next[slot]) node->next[slot] = new TrieNode();
                    node = node->next[slot];
                    node->index = index;  // words arrive in order, so this keeps the largest
                }
            }
        }
    }

    int f(string pref, string suff) {
        TrieNode* node = root;
        for (char ch : suff + '{' + pref) {
            node = node->next[ch - 'a'];
            if (!node) return -1;
        }
        return node->index;
    }
};
class TrieNode:
    __slots__ = ('children', 'index')  # up to ~640,000 nodes, so keep each one small

    def __init__(self):
        self.children = {}
        self.index = -1  # largest index of a word whose stored string passes through here


class WordFilter:
    def __init__(self, words: list[str]):
        self.root = TrieNode()
        for index, word in enumerate(words):
            for start in range(len(word)):
                node = self.root
                for ch in word[start:] + '{' + word:
                    if ch not in node.children:
                        node.children[ch] = TrieNode()
                    node = node.children[ch]
                    node.index = index  # words arrive in order, so this keeps the largest

    def f(self, pref: str, suff: str) -> int:
        node = self.root
        for ch in suff + '{' + pref:
            if ch not in node.children:
                return -1
            node = node.children[ch]
        return node.index
class WordFilter {
    private static class TrieNode {
        TrieNode[] next = new TrieNode[27];  // 'a'..'z', then '{', the character right after 'z'
        int index = -1;                      // largest index of a word whose stored string passes here
    }

    private final TrieNode root = new TrieNode();

    public WordFilter(String[] words) {
        for (int index = 0; index < words.length; index++) {
            String word = words[index];
            for (int start = 0; start < word.length(); start++) {
                String stored = word.substring(start) + "{" + word;
                TrieNode node = root;
                for (char ch : stored.toCharArray()) {
                    int slot = ch - 'a';
                    if (node.next[slot] == null) node.next[slot] = new TrieNode();
                    node = node.next[slot];
                    node.index = index;  // words arrive in order, so this keeps the largest
                }
            }
        }
    }

    public int f(String pref, String suff) {
        TrieNode node = root;
        for (char ch : (suff + "{" + pref).toCharArray()) {
            node = node.next[ch - 'a'];
            if (node == null) return -1;
        }
        return node.index;
    }
}

Complexity Analysis

Let N be the number of words and L their maximum length (at most 7).

Time Complexity:

  • Constructor: O(N · L²). Each word stores L strings, each at most 2L + 1 characters long, and the walk does constant work per character. A 7-letter word costs 84 steps instead of the hash map's 441 characters. At full size (10,000 random 7-letter words) the build took about 0.02 s in C++, against 0.07 s for the hash map.
  • f: O(p + s). One step per character of the key, and no hashing.

Space Complexity: O(N · L²) nodes in the worst case, when no two stored strings share a beginning.

One honest caveat about memory. The big-O is smaller than the hash map's O(N · L³), but each node here reserves 27 child slots (C++ and Java) or holds its own small dictionary (Python). At these limits, where L is only 7, that overhead wins: at full size the whole program peaked at about 139 MB in C++ (hash map: 36 MB), 157 MB in Python (74 MB) and 170 MB in Java (132 MB). Both approaches answer every query in O(p + s). The trie does less work to build and scales better as words get longer. The hash map is the lighter choice when memory is the tighter budget.