745. Prefix and Suffix Search

Hard

String,Design,Trie

---

Design a special dictionary with some words that searchs 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.

---

Submissions

Time Submitted	Status	Runtime	Memory	Language
06/18/2022 12:01	Accepted	450 ms	255.6 MB	java
06/18/2022 11:41	Accepted	551 ms	257.3 MB	java
06/18/2022 11:40	Accepted	1177 ms	151.8 MB	cpp
06/18/2022 11:40	Time Limit Exceeded	N/A	N/A	cpp
06/18/2022 11:39	Accepted	1135 ms	151.8 MB	cpp
06/18/2022 11:37	Accepted	457 ms	254.8 MB	java