Prefix and Suffix Search Problem

Prefix and Suffix Search Problem — ExecCode Hard DSA Practice

Solve the Prefix and Suffix Search problem on ExecCode. Free online hard DSA practice in Design. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Design a search structure over a fixed list of words that answers f(prefix, suffix): return the largest index of a word that has the given prefix AND the given suffix, or -1 if none match. The classic trick is to insert every (suffix + "#" + word) combination into one combined trie so a single lookup of (suffix + "#" + prefix) answers the query.

Examples

Input words = ["apple"], queries = ["a|e", "b|"]; Output [0, -1]. Input words = ["apple", "banana"], queries = ["ban|na", "ap|le", "c|"]; Output [1, 0, -1]. Input words = ["cat", "car", "dog"], queries = ["ca|t", "ca|r", "d|g"]; Output [0, 1, 2]

Constraints

1 <= words.length <= 10^4 1 <= words[i].length <= 7 1 <= queries <= 10^4 words[i] and every prefix/suffix consist of lowercase English letters

Practice Prefix and Suffix Search free on ExecCode. Browse DSA problems, topic map, and placement guides.