Skip to main content
Talentd

Prefix and Suffix Search - Solution & Explanation

HardArrayHash TableStringDesign8 min readAsked at: Microsoft, Meta, Google
Practice this problem

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:

Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".

 

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.

Approach Overview

Problem Overview: You receive a list of words and must design a structure that returns the highest index of a word matching both a given prefix and suffix. Each query asks for f(prefix, suffix). The challenge is handling many queries efficiently while checking both ends of the word.

Approach 1: Hash Map with Pre-computed Prefix-Suffix Pairs (Preprocessing O(n * L²), Query O(1))

Precompute every possible (prefix, suffix) combination for each word and store the latest index in a hash map. For a word of length L, generate all prefixes and suffixes using nested loops and map prefix + "#" + suffix to the word index. When a query arrives, construct the same key and perform a constant-time hash lookup. The tradeoff is memory usage: preprocessing costs O(n * L²) time and space because every prefix-suffix pair is stored. The benefit is extremely fast queries. This method relies heavily on fast lookups provided by a hash table and works well when the number of queries is large.

Approach 2: Trie with Combined Prefix and Suffix Key (Build O(n * L²), Query O(L))

A more structured approach uses a Trie. For each word, insert all combinations of suffix + '#' + word into the trie. The separator ensures prefix and suffix segments remain distinguishable during traversal. Each node stores the latest index of the word passing through it. During a query, search the trie for suffix + '#' + prefix. If traversal succeeds, the stored index is the answer. This approach reduces query work to O(L) where L is the prefix/suffix length. The build phase still costs O(n * L²) because every suffix contributes multiple insertions. Tries handle overlapping strings efficiently and are common in advanced string search problems.

Approach 3: Brute Force Scan (Query O(n * L))

The simplest idea checks every word for each query. For each word, verify the prefix using a string comparison and check the suffix using substring or reverse indexing. Track the largest index that satisfies both conditions. This requires scanning all words per query, producing O(n * L) time per call and O(1) extra space. It works for very small inputs but fails when the number of queries grows.

Recommended for interviews: The trie-based design is the approach most interviewers expect because it demonstrates understanding of efficient string indexing and custom data structures. Explaining the brute force solution first shows baseline reasoning. Then moving to a trie or precomputed hash map demonstrates the optimization needed for repeated queries.

Approach 1: Trie with Combined Prefix and Suffix Key

This approach leverages the use of a Trie (prefix tree), where each node can store a unique combination of prefix and suffix of words. By combining prefixes and suffixes into a single key when inserting the words and when querying, one can efficiently determine if a word with a given prefix and suffix exists.

This Python solution constructs a Trie where each possible prefix-suffix combination maps to the index of the most recently added word with that combination. When querying with a prefix and a suffix, the function builds a search key by appending the suffix, a delimiter '#', and the prefix, and traverses the Trie according to this composite key.

Code

PythonJava

Python

Java

Complexity

Time complexity is O(W^2) for initialization where W is the average length of words. Query time complexity is O(P + S), where P and S are the lengths of the prefix and suffix respectively. Space complexity is O(W^2 * N) for the Trie, where N is the number of words.

Try this approach in the editor →

Approach 2: Hash Map with Pre-computed Indices

This approach involves storing each word’s prefix and suffix combinations in a hash map, along with its index. During query operations, the hash map is used to look up the word using a prefix and suffix combination.

In this C++ solution, a hash map is used where each key is formed by concatenating every possible prefix and suffix of each word, using a delimiter '#'. These keys are mapped to the index of the words. Querying involves checking if the prefix-suffix combined key exists in the hash map.

Code

C++JavaScript

C++

JavaScript

Complexity

Time complexity is O(W^2 * N) for preprocessing and O(1) for query. Space complexity is O(W^2 * N), where W is the word length and N is the number of words.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Trie with Combined Prefix and Suffix Key

Time complexity is O(W^2) for initialization where W is the average length of words. Query time complexity is O(P + S), where P and S are the lengths of the prefix and suffix respectively. Space complexity is O(W^2 * N) for the Trie, where N is the number of words.

Hash Map with Pre-computed Indices

Time complexity is O(W^2 * N) for preprocessing and O(1) for query. Space complexity is O(W^2 * N), where W is the word length and N is the number of words.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n * L) per queryO(1)Small inputs or quick prototype without preprocessing
Hash Map with Precomputed Prefix-SuffixBuild: O(n * L²), Query: O(1)O(n * L²)Best when query count is very high and memory is acceptable
Trie with Combined Prefix-Suffix KeyBuild: O(n * L²), Query: O(L)O(n * L²)Interview-friendly design for fast prefix/suffix lookups

Video Solution

Prefix and Suffix Search | Live Coding with Explanation | Leetcode - 745 • Algorithms Made Easy • 10,864 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Prefix and Suffix Search easy or hard?
Prefix and Suffix Search is classified as a Hard problem because it requires designing a custom data structure optimized for repeated queries. The difficulty comes from combining prefix and suffix matching efficiently without scanning all words.
Prefix and Suffix Search Python/Java solution
Python and Java implementations usually follow the trie-based approach or the hash map precomputation approach. The trie version stores the latest index at each node, while the hash map version maps 'prefix#suffix' directly to the index for constant-time queries.
How to solve Prefix and Suffix Search in O(1)?
Precompute all prefix and suffix combinations for each word and store them in a hash map keyed by 'prefix#suffix'. Each key maps to the largest index of a matching word. After preprocessing in O(n * L²), each query becomes a single hash lookup in O(1).
What is the best approach for Prefix and Suffix Search?
The trie with combined suffix and prefix keys is the most common optimal design. Each word inserts entries like suffix + '#' + word into the trie, allowing queries to search for suffix + '#' + prefix in O(L) time. Preprocessing costs O(n * L²), but queries become very efficient.
Is Prefix and Suffix Search asked at Google/Amazon/Meta?
This problem represents a class of string indexing and trie design questions commonly asked at large tech companies including Google, Amazon, and Meta. Variations often involve prefix matching, suffix queries, or autocomplete-style data structures.
What data structure is used in Prefix and Suffix Search?
The optimal solutions use either a Trie for efficient string traversal or a Hash Map for constant-time prefix-suffix lookups. The trie version stores combined keys like 'suffix#word' while the hash map stores all prefix-suffix pairs.
What is the time complexity of Prefix and Suffix Search?
Using a trie or precomputed hash map, preprocessing takes O(n * L²) where n is the number of words and L is the maximum word length. Query time is O(L) for the trie approach or O(1) for the hash map approach. A naive scan would take O(n * L) per query.

Ready to solve this problem?

Practice Prefix and Suffix Search with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Add and Search Words Data Structure