Prefix And Suffix Search - Leetcode Solution

Problem Description:

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix).

It will return the word with given prefix and suffix with the maximum weight. If no word exists, return -1.

Example:

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") # returns 0
WordFilter.f("b", "") # returns -1

Solution:

One simple solution for the problem would be to store all the words in a list and then for each query, traverse through the list to find the words that contain the given prefix and suffix. As we are checking for multiple queries, this would lead to a poor time complexity O(n * q), where n is the number of words and q is the number of queries.

A more optimized solution would be to use a Trie data structure to store the words. Each Trie node would store a map of characters to their children. We also store a list of words that end at a Trie node. This list will help in filtering words with a particular suffix.

To handle prefix search, we can traverse through the Trie nodes with the given prefix. Then, we get all the words from the Trie nodes that contain the given suffix. We then return the word with the maximum weight from these words.

The time complexity of this solution is O(p^2 + wlogw), where p is the length of the prefix, w is the number of words, and logw is the time required to sort the list of words with a given suffix. Sorting is required to obtain the word with maximum weight.

The Python implementation for the solution is given below:

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

class WordFilter:
    
    def __init__(self, words: List[str]):
        self.root = TrieNode()
        for i, word in enumerate(words):
            self.add_word_to_trie(word, i)

    def add_word_to_trie(self, word, weight):
        node = self.root
        node.words.append(weight)
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
            node.words.append(weight)
    
    def f(self, prefix: str, suffix: str) -> int:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return -1
            node = node.children[c]
        
        end_words = []
        for word_weight in node.words:
            word = words[word_weight]
            if word.endswith(suffix):
                end_words.append(word_weight)
                
        if not end_words:
            return -1
        return max(end_words)

In the above implementation, TrieNode is a class that represents a node of a Trie data structure. add_word_to_trie function adds a word to the Trie data structure. The function f performs the search operation and returns the word with the maximum weight that contains the given prefix and suffix.

1