Log inSign up
hardLeetCodeNot Started

Prefix and Suffix Search

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

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

Implement the WordFilter class: - WordFilter(string[] words) Initializes the object with the words in the dictionary. - f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.

Example 1 · Example 1: Single word dictionary:

Input: WordFilter(["apple"]); f("a", "e"); f("b", "");
Output: [0, -1]
Explanation: - "apple" starts with "a" and ends with "e" -> index 0. - No word starts with "b" -> -1. Trie entries inserted for "apple": "apple{apple", "pple{apple", "ple{apple", "le{apple", "e{apple", "{apple"

Constraints:

  • 1 <= words.length <= 104
  • 1 <= words[i].length <= 7
  • 1 <= pref.length, suff.length <= 7
  • words[i], pref and suff consist of lowercase English letters only.
  • At most 104 calls will be made to the function f.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master string unification transformations (suffix + delimiter + prefix).
  • Use ASCII delimiter trick (char '{' at index 26) to cleanly extend Trie alphabet.
  • Achieve O(L) query speed by shifting computation into initialization.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Simultaneous prefix and suffix matching requirements.
  • Small word length (L <= 7) with high query volume (Q = 10,000).
  • Must return maximum index on multiple matches.

Algorithmic Decision Tree:

  • Notice L <= 7 is small: each word has only L + 1 suffixes.
  • Wrap each word into suffix + '{' + word for all suffixes.
  • In f(pref, suff), query suff + '{' + pref down the Trie in O(L) time.

Connected Patterns:

Implement Trie (Prefix Tree)Design Add and Search WordsSuffix Automaton

1. Backward Linear Search

Intuition

Store original words array. For f(pref, suff), loop from i = words.size() - 1 down to 0. If words[i].startsWith(pref) and words[i].endsWith(suff), return i. If loop completes, return -1.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Store words array.
  2. Step 2: f(pref, suff): loop i from N-1 down to 0.
  3. Step 3: If w.startsWith(pref) and w.endsWith(suff), return i.
  4. Step 4: Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6class WordFilter {
7 vector<string> dict;
8public:
9 WordFilter(vector<string>& words) {
10 dict = words;
11 }
12
13 int f(string pref, string suff) {
14 int pLen = pref.length(), sLen = suff.length();
15 for (int i = dict.size() - 1; i >= 0; i--) {
16 const string& w = dict[i];
17 int wLen = w.length();
18 if (wLen >= pLen && wLen >= sLen) {
19 if (w.rfind(pref, 0) == 0 && w.compare(wLen - sLen, sLen, suff) == 0) {
20 return i;
21 }
22 }
23 }
24 return -1;
25 }
26};
27
28int main() {
29 vector<string> words = {"apple"};
30 WordFilter wf(words);
31 cout << "f('a', 'e'): " << wf.f("a", "e") << endl;
32 cout << "f('b', ''): " << wf.f("b", "") << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: Init: O(1), f: O(N * L) — Must inspect every word backwards for each query.
  • Space complexity: O(N * L) — Stores words array.

Why Brute Force Doesn't Scale:

Linear scan per query exhausts time limits on high query loads.

Unified Trie answers all 10,000 queries in ~15ms total.

2. Hash Map of (Prefix, Suffix) Pairs

Intuition

For each word at index weight, generate all possible prefix substrings p (length 1 to L) and suffix substrings s (length 1 to L). Store in map[p + '#' + s] = weight.

When to apply: Fast lookup when memory allows storing all prefix-suffix string combinations.

Algorithm

  1. Step 1: Map pair -> largest_index.
  2. Step 2: For each word, generate all prefixes and suffixes.
  3. Step 3: map[prefix + '#' + suffix] = i.
  4. Step 4: f(pref, suff): return map[pref + '#' + suff] or -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5using namespace std;
6
7class WordFilter {
8 unordered_map<string, int> pairMap;
9public:
10 WordFilter(vector<string>& words) {
11 for (int i = 0; i < (int)words.size(); i++) {
12 const string& w = words[i];
13 int len = w.length();
14 for (int p = 0; p <= len; p++) {
15 string pref = w.substr(0, p);
16 for (int s = 0; s <= len; s++) {
17 string suff = w.substr(len - s);
18 pairMap[pref + "#" + suff] = i;
19 }
20 }
21 }
22 }
23
24 int f(string pref, string suff) {
25 string key = pref + "#" + suff;
26 return pairMap.count(key) ? pairMap[key] : -1;
27 }
28};
29
30int main() {
31 vector<string> words = {"apple"};
32 WordFilter wf(words);
33 cout << "f('a', 'e'): " << wf.f("a", "e") << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: Init: O(N * L^2), f: O(L) — Each word has at most (L+1)^2 <= 64 prefix-suffix pairs. Map lookup takes O(L).
  • Space complexity: O(N * L^2) — Stores all pair combinations in hash map.

3. Combined Suffix-Delimiter-Word Trie

Intuition

Each node has children[27] (index 26 corresponds to {) and integer weight. For each word of index i, loop suffix index from 0 to L. Form suffix + '{' + word. Insert into Trie, updating node.weight = i on every visited node. Query f(pref, suff) searches suff + '{' + pref down the Trie, returning curr.weight in O(|pref| + |suff|) time.

When to apply: Standard optimal solution with superior cache performance and zero hash collision overhead.

Algorithm

  1. Step 1: Define TrieNode with children[27] and weight = -1.
  2. Step 2: Helper charToIndex(c): return c == '{' ? 26 : c - 'a'.
  3. Step 3: For each word at index i, for each suffix start k from 0 to L: insert word.substr(k) + '{' + word, updating curr.weight = i on each node.
  4. Step 4: f(pref, suff): walk Trie with suff + '{' + pref. If any child is null, return -1. At end, return curr.weight.

Interactive Trace for Unified Trie Query

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Build query string target = suff + '{' + pref = "e{a"
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'e'
weight: 0

Node order shown; add connections to display explicit tree edges.

curr: e
Check / comparison
Walk char 'e'
Decision / next transition
Move to child 'e'.
Why this step matters

Step 1: Build query string target = suff + '{' + pref = "e{a". Start at root.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[27];
8 int weight;
9 TrieNode() : weight(-1) {
10 for (int i = 0; i < 27; i++) children[i] = nullptr;
11 }
12};
13
14class WordFilter {
15 TrieNode* root;
16
17 int charIdx(char c) {
18 return c == '{' ? 26 : c - 'a';
19 }
20
21 void insert(const string& str, int weight) {
22 TrieNode* curr = root;
23 for (char c : str) {
24 int idx = charIdx(c);
25 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
26 curr = curr->children[idx];
27 curr->weight = weight;
28 }
29 }
30
31public:
32 WordFilter(vector<string>& words) {
33 root = new TrieNode();
34 for (int i = 0; i < (int)words.size(); i++) {
35 const string& w = words[i];
36 int len = w.length();
37 for (int k = 0; k <= len; k++) {
38 string combined = w.substr(k) + "{" + w;
39 insert(combined, i);
40 }
41 }
42 }
43
44 int f(string pref, string suff) {
45 TrieNode* curr = root;
46 string target = suff + "{" + pref;
47 for (char c : target) {
48 int idx = charIdx(c);
49 if (!curr->children[idx]) return -1;
50 curr = curr->children[idx];
51 }
52 return curr->weight;
53 }
54};
55
56int main() {
57 vector<string> words = {"apple"};
58 WordFilter wf(words);
59 cout << "Optimal f('a', 'e'): " << wf.f("a", "e") << endl;
60 cout << "Optimal f('b', ''): " << wf.f("b", "") << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: Init: O(N * L^2), f: O(|pref| + |suff|) — Inserts at most L+1 strings of length <= 15 for each of N words. Query is strictly linear in query length (<= 15 operations).
  • Space complexity: O(N * L^2 * 27) — Trie nodes allocate 27 pointers each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Scan All Words BackwardsInit: O(1), f: O(N * L)O(N * L)Store words array. On f(pref, suff), scan from index N-1 down to 0; return first word matching both prefix and suffix.Linear scan per query.
2.Better — Two Tries with IntersectionInit: O(N * L), f: O(L + K log K)O(N * L)Maintain a prefix Trie and a reversed suffix Trie storing sorted list of word indices. Find intersection of index lists.Intersecting index lists during queries.
3.Optimal — Combined Wrapped Suffix+Word TrieOptimalInit: O(N * L^2), f: O(|pref| + |suff|)O(N * L^2 * 27)Insert suffix + '{' + word into a 27-ary Trie for all suffixes. Store max weight at every node.None. Industry gold standard for LeetCode 745.

Common Pitfalls & Crucial Edge Cases

Forgetting character '{' in alphabet size

Sizing children array to 26 causes out-of-bounds on delimiter {.

Rebuilding query searches with two separate Tries

Intersecting index lists during queries is far slower than the unified Trie approach.

Not updating node weight during traversal

Failing to update curr.weight on intermediate nodes prevents prefix matching from retrieving the largest index.

Crucial Edge Cases to Validate:

  • Multiple words match prefix and suffix — Later inserted words override weight at Trie nodes, automatically returning maximum index.
  • Empty prefix or empty suffix — Handled cleanly as valid boundary substrings.
  • No matching word in dictionary — Query terminates on null pointer and returns -1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the clever unification trick: combining suffix and prefix with a delimiter reduces two constraints to a single prefix lookup.
  2. Justify the space complexity: since words are short (length <= 7), storing suffixes creates at most 8 insertions per word.
  3. Highlight that query time is strictly O(|pref| + |suff|), executing in less than 15 operations per query.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the character { used as the delimiter in the combined string?

2.What is the query time complexity of f(pref, suff) in the optimal Trie implementation?

Back to DSA Sheet