We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Prefix and Suffix Search

Number: 746

Difficulty: Hard

Paid? No

Companies: Google, TikTok, Meta

Problem Description

Design a special dictionary that allows searching for words by both a given prefix and suffix. Implement a class WordFilter that takes an array of words during initialization. It should support a function f(pref, suff) that returns the index of the word (with the largest index, if multiple exist) which has the given prefix and suffix. If no such word exists, return -1.

Key Insights

  • Precompute and store all possible prefix and suffix combinations from each word.
  • Given the small maximum word length (7), it is feasible to generate every possible (prefix, suffix) pair.
  • Use a delimiter (like "#") to combine prefix and suffix into a single key.
  • Update the mapping with the current index to ensure that the answer is always the largest index for overlapping pairs.
  • Trade-off between time spent during initialization and fast O(1) query lookups.

Space and Time Complexity

Time Complexity:

  • Constructor: O(N * L^2) per word, where L is the length of the word (with L ≤ 7) and N is the number of words (up to 10⁴). This is acceptable as L is very small.
  • Query f: O(1) average lookup time.

Space Complexity:

  • O(N * L^2) extra space for storing the dictionary of all prefix-suffix combinations.

Solution

The solution precomputes all possible prefixes and suffixes for every word and stores them in a dictionary (or hash map). For each word, every possible prefix (from the empty string up through the full word) and every possible suffix (from the full word down to the empty string) is generated. These are concatenated together with a special character (e.g. "#") to form a unique key in the dictionary. The value stored is the current word's index. This guarantees that when multiple words share the same prefix and suffix, the one with the larger index overwrites the previous index. During a query f(pref, suff), a single lookup on the dictionary provides the answer instantly.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java.

class WordFilter:
    def __init__(self, words):
        # Initialize the dictionary (lookup) to store all prefix-suffix combinations.
        self.lookup = {}
        for index, word in enumerate(words):
            L = len(word)
            # Generate all possible prefixes and suffixes.
            for i in range(L + 1):
                prefix = word[:i]
                for j in range(L + 1):
                    suffix = word[j:]
                    # Create a key by concatenating prefix and suffix with a '#'
                    self.lookup[prefix + '#' + suffix] = index
                    
    def f(self, pref, suff):
        # Retrieve the index if the key exists; otherwise, return -1.
        return self.lookup.get(pref + '#' + suff, -1)
← Back to All Questions