Prefix and Suffix Search — Combined Key Trie

Problem

Design a class that finds the largest index word with given prefix AND suffix.

Approach — Combined Key Trick

For word w at index i, insert suf#{w} for each suffix suf of w into a hash map. For query (prefix, suffix), lookup suffix#{prefix}.

Time: O(n * L²) build, O(L) query | Space: O(n * L²)

Solutions

Python

class WordFilter:
    def __init__(self, words: list[str]):
        self.lookup={}
        for idx,w in enumerate(words):
            for i in range(len(w)+1):
                key=w[i:]+'#'+w
                self.lookup[key]=idx
    def f(self, pref: str, suff: str) -> int:
        return self.lookup.get(suff+'#'+pref,-1)

Complexity

• Build: O(n * L²) | Query: O(L)