Prefix and Suffix Search
Prefix and Suffix Search 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.
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
- Design Patterns pattern guide
- Tries subpattern
- The full DSA patterns sheet
- All coding practice problems
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
- Implement Trie (Prefix Tree) — Medium, same subpattern
- Longest Word in Dictionary — Easy, same subpattern
- Replace Words — Medium, same subpattern
- Word Squares — Hard, same subpattern
- All O`one Data Structure — Hard, same pattern