745. Prefix and Suffix Search
Prefix and Suffix Search (LeetCode 745) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Tries subpattern.
How to solve Prefix and Suffix Search
Prefix and Suffix Search is a Trie Implementation problem, part of Design Patterns. Implement Trie data structure for prefix-based operations and autocomplete systems.
Work towards the solution in these steps:
- Consider using a Trie data structure to efficiently support prefix searches across the given words.
- Since you need to check both prefix and suffix, think about how you might combine or modify tries to handle suffix queries as well.
- One approach is to encode each word in a way that allows simultaneous prefix and suffix searching by merging them into a single searchable structure.
The reference solution runs in O(n) time and O(t) space.
The Prefix and Suffix Search solution and editorial walks through the full approach with reference code.
Problem statement
Design a special dictionary which has some words and allows you to search 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 prefix, string suffix) Returns the index of the word in the dictionary which 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 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 <= 15000 1 <= words[i].length <= 10 1 <= prefix.length, suffix.length <= 10 words[i], prefix and suffix consist of lower-case English letters only.
At most 15000 calls will be made to the function f.
Topics and companies
Topics: Trie.
Reported in interviews at Amazon, Facebook.
How to practise Prefix and Suffix Search on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(t) space.
Open Prefix and Suffix Search in the code editor, or read the Prefix and Suffix Search editorial for a worked solution with its approach and complexity analysis.
Where Prefix and Suffix Search sits in the DSA pattern sheet
Problems related to Prefix and Suffix Search
Other problems that use the same Tries and Design Patterns techniques:
- Design Add and Search Words Data Structure — Medium, same subpattern
- Extra Characters in a String — Medium, same subpattern
- Implement Trie (Prefix Tree) — Medium, same subpattern
- Longest Word in Dictionary — Easy, same subpattern
- Replace Words — Medium, same subpattern
- Word Squares — Hard, same subpattern
Prefix and Suffix Search FAQ
What is the LeetCode number of Prefix and Suffix Search?
Prefix and Suffix Search is LeetCode problem 745, rated Hard.
What pattern is used to solve Prefix and Suffix Search?
Prefix and Suffix Search is a Trie Implementation problem. It belongs to the Design Patterns pattern, in the Tries subpattern.
What is the time complexity of Prefix and Suffix Search?
The reference solution runs in O(n) time and O(t) space.
Which companies ask Prefix and Suffix Search?
Prefix and Suffix Search has been reported in interviews at Amazon, Facebook.