Prefix and Suffix Search — Combined Key Trie Trick

Problem Statement#

LeetCode 745 — Prefix and Suffix Search | Difficulty: Hard

Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the WordFilter class:

• WordFilter(words) initialises the object with the words in the dictionary.
• f(prefix, suffix) returns the index of the word in the dictionary that has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word, return -1.

Constraints:

• 1 <= words.length <= 10^4
• 1 <= words[i].length <= 7
• 1 <= prefix.length, suffix.length <= 7
• prefix and suffix consist of lowercase English letters.
• At most 10^4 calls to f.

Examples:

WordFilter w = new WordFilter(["apple"])
w.f("a", "e")  → 0   ("apple" starts with "a" and ends with "e")

WordFilter w = new WordFilter(["apple", "ape", "able"])
w.f("a", "e")  → 1   (both apple and ape match; ape has higher index? actually apple=0, ape=1, able=2; "ape" has suffix "e" too. Largest matching index = 1.)

Why This Problem Matters#

Prefix-and-suffix search is the canonical "two-dimensional trie query" problem. Asked at Google, Amazon, and Bloomberg, it tests whether you can compose data structures creatively. The standard tricks (one trie for prefix, one for suffix, then intersect) work but are slow; the elegant solution combines suffix and prefix into a single key, reducing the query to a plain trie walk.

The technique — concatenating two views of the same string with a separator — appears in suffix arrays, Burrows-Wheeler transforms, and search-engine indexing. Once you see it here, you will spot it everywhere.

The Core Insight#

For a word w, build the combined key set suffix + "#" + w for every suffix of w. Insert every such key into a trie, tagging each node along the path with the latest word index that visits it. To answer f(prefix, suffix), query the trie with suffix + "#" + prefix — the matching nodes inherently match both halves.

Why this works: the prefix prefix of w is preserved verbatim after the #. The query suffix + "#" + prefix matches paths where the trie walk first traverses an actual suffix of some word, then crosses the separator, then matches the prefix. Tagging each node with the latest visiting index gives us the largest matching index for free.

The # separator ensures we never confuse a real character with the boundary; any character not in the alphabet works.

Visual Dry Run#

Words: ["apple"] (index 0). Suffixes of "apple": apple, pple, ple, le, e. Combined keys with #:

"apple#apple"
"pple#apple"
"ple#apple"
"le#apple"
"e#apple"

Insert all five into the trie, marking every node with index 0.

Query f("a", "e") → look up "e#a":

Walk: e → #  → a
At each node visited, the index 0 is recorded.
Return 0.

The walk crossed the separator from "e" (suffix part) into "a" (prefix part), and node 'a' was tagged with index 0 → answer 0.

If we then add "ape" (index 1) and "able" (index 2), the new combined keys for "ape" are ape#ape, pe#ape, e#ape. Re-querying f("a","e") now reaches the e # a node from "e#ape", updating the tag to 1. Answer becomes 1.

Solution (Optimal) — Combined-Key Trie#

Python#

class TrieNode:
    __slots__ = ("children", "weight")
    def __init__(self):
        self.children = {}
        self.weight = -1   # latest word index that visited
 
class WordFilter:
    def __init__(self, words: list[str]):
        self.root = TrieNode()
        for idx, w in enumerate(words):
            # Insert every suffix#word combination
            for i in range(len(w) + 1):
                key = w[i:] + "#" + w
                node = self.root
                for ch in key:
                    node = node.children.setdefault(ch, TrieNode())
                    node.weight = idx     # newest index dominates
 
    def f(self, prefix: str, suffix: str) -> int:
        key = suffix + "#" + prefix
        node = self.root
        for ch in key:
            if ch not in node.children:
                return -1
            node = node.children[ch]
        return node.weight

JavaScript#

class WordFilter {
  constructor(words) {
    this.root = { children: {}, weight: -1 };
    for (let idx = 0; idx < words.length; idx++) {
      const w = words[idx];
      for (let i = 0; i <= w.length; i++) {
        const key = w.slice(i) + "#" + w;
        let node = this.root;
        for (const ch of key) {
          if (!node.children[ch]) node.children[ch] = { children: {}, weight: -1 };
          node = node.children[ch];
          node.weight = idx;
        }
      }
    }
  }
 
  f(prefix, suffix) {
    const key = suffix + "#" + prefix;
    let node = this.root;
    for (const ch of key) {
      if (!node.children[ch]) return -1;
      node = node.children[ch];
    }
    return node.weight;
  }
}

Complexity#

• Build: O(N times K^2) where N = number of words, K = max word length (each word contributes K suffix-keys of length 2K).
• Query: O(P + S) where P = prefix length, S = suffix length.
• Space: O(N times K^2) for the trie nodes.

Common Mistakes#

1. Building two separate tries (prefix and suffix) and intersecting — works but query becomes O(prefix matches times suffix matches) and is much slower.
2. Using a separator that could appear in the input — if your input alphabet includes #, switch to \0 or any unused codepoint.
3. Not updating the weight at every node along the insertion path — the largest matching index may bind at an internal node, not the terminal.
4. Inserting only the full word#word key — misses queries like f("a", "le") where the suffix is shorter than the word.
5. Forgetting i = len(w) (empty suffix) — needed for queries with an empty suffix; problem says length >=1 so optional, but safer to include.
6. Storing word indices in a list per node — wastes memory; the latest index alone suffices because we want the largest.

Interview Tips#

• Walk through the suffix-pair generation explicitly: "for each suffix of the word, concatenate suffix # word."
• Justify the separator: it prevents the suffix and prefix portions from blending mid-character.
• State that we always overwrite the node weight on insert because we want the largest valid index.
• Highlight that query is plain trie walk — no intersection, no merge.
• Mention the K^2 build cost is acceptable because K <= 7 — total characters per word is at most 56.

Follow-up Questions#

• What if words have lengths up to 10^5? Build cost K^2 explodes; switch to building one prefix trie and one suffix trie, then intersect via word-id sets.
• Allow any matching index, not just largest? Store a sorted list (or set) of indices per node and return any.
• Streaming inserts? The trie supports incremental inserts; queries remain O(P + S).
• Counting matches instead of returning index? Add a counter at each node tracking "words visiting this node."
• What if the alphabet is huge (Unicode)? Use a hash-map trie; the algorithm is identical.

Key Takeaways#

• Combined-key trie collapses 2D prefix-and-suffix search into 1D trie walk.
• Insert every suffix + "#" + word so any (prefix, suffix) query rendezvous on the separator.
• Always overwrite weight on insert to track the largest matching index.
• Query is O(P + S) — no intersection, no merge, no scan.
• The separator must not appear in the input alphabet; pick # or \0.
• Mastering this unlocks suffix-array-like problems, BWT-style indexing, and other 2D string queries.