Skip to main content

745 - Prefix and Suffix Search

Difficulty: Hard | Pattern: Trie / HashMap | Company tags: Google, Amazon

Problem Statement​

Design a special dictionary that searches 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 pref, String suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. 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:

WordFilter wf = new WordFilter(["apple"]);
wf.f("a", "e") → 0
wf.f("b", "") → -1

Approach: Precompute All (prefix, suffix) Pairs — O(n × L²), O(n × L²)​

Key insight: For each word, generate all (prefix, suffix) pairs and store the word's index in a hashmap. For duplicate pairs, store the highest index.

class WordFilter:
    def __init__(self, words: list[str]):
        self.lookup = {}
        for idx, word in enumerate(words):
            n = len(word)
            for i in range(n + 1):       # prefix lengths 0..n
                for j in range(n + 1):   # suffix lengths 0..n
                    key = (word[:i], word[n-j:] if j > 0 else "")
                    self.lookup[key] = idx
    
    def f(self, pref: str, suff: str) -> int:
        return self.lookup.get((pref, suff), -1)

Alternative: Joined Key Trick — O(n × L²) build, O(1) query​

Encode each (prefix, suffix) pair as prefix + "#" + suffix string — faster in practice.

class WordFilter:
    def __init__(self, words):
        self.lookup = {}
        for i, word in enumerate(words):
            n = len(word)
            for p in range(n + 1):
                for s in range(n + 1):
                    key = word[:p] + '#' + word[n-s:]
                    self.lookup[key] = i
    
    def f(self, pref, suff):
        return self.lookup.get(pref + '#' + suff, -1)

Complexity​

  • Build Time: O(n × L²) where L = max word length
  • Query Time: O(L) for string hashing
  • Space: O(n × L²)

Trade-off​

For large dictionaries and many queries, a Trie-based approach is more memory efficient. For interview, the hash map approach is simpler to implement correctly.