LeetCode Solutions Blog

Prefix and Suffix Search

Difficulty: Hard

Problem Description

Design a special dictionary that searches the words in it by a prefix and a suffix. Implement the WordFilter class with methods to initialize the object with words and to search for words based on given prefix and suffix.

Key Insights

The problem requires efficient searching of words based on both prefix and suffix.
Using a Trie (prefix tree) can help in efficiently managing and searching prefixes.
To handle suffixes, we can reverse the strings and apply a similar Trie structure.
The solution needs to ensure that if multiple words match, the highest index is returned.

Space and Time Complexity

Time Complexity: O(n * m) for initialization, where n is the number of words and m is the maximum length of the words. Each search operation f(pref, suff) takes O(p + s) where p is the length of the prefix and s is the length of the suffix.

Space Complexity: O(n * m) for storing the words in the Trie structures.

Solution

The solution utilizes two Trie data structures: one for storing the words to handle prefix searches and another for handling suffix searches by storing the reversed words. When searching, we check for matches in both Tries and return the highest index of the matching words.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.indexes = []

class WordFilter:
    def __init__(self, words):
        self.prefix_trie = TrieNode()
        self.suffix_trie = TrieNode()
        
        for index, word in enumerate(words):
            # Insert into prefix Trie
            node = self.prefix_trie
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                node.indexes.append(index)
            
            # Insert into suffix Trie (reverse the word)
            node = self.suffix_trie
            for char in reversed(word):
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                node.indexes.append(index)

    def f(self, pref, suff):
        # Search in prefix Trie
        node = self.prefix_trie
        for char in pref:
            if char not in node.children:
                return -1
            node = node.children[char]

        prefix_indexes = set(node.indexes)

        # Search in suffix Trie
        node = self.suffix_trie
        for char in reversed(suff):
            if char not in node.children:
                return -1
            node = node.children[char]

        suffix_indexes = set(node.indexes)

        # Find the maximum index that is in both sets
        valid_indexes = prefix_indexes.intersection(suffix_indexes)
        return max(valid_indexes) if valid_indexes else -1