Introduction

In this blog post, we will explore how to solve the LeetCode problem "745" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 1: Input ["WordFilter", "f"] [[["apple"]], ["a", "e"]] Output [null, 0] Explanation WordFilter wordFilter = new WordFilter(["apple"]); wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e". Constraints: 1 <= words.length <= 104 1 <= words[i].length <= 7 1 <= pref.length, suff.length <= 7 words[i], pref and suff consist of lowercase English letters only. At most 104 calls will be made to the function f.

Explanation

Here's a solution to the word filter problem, focusing on efficiency:

• Trie-based indexing: Build two Tries: one for prefixes and one for reversed suffixes. This allows for efficient prefix and suffix searching.
• Intersection of word indices: For a given prefix and suffix, find the indices of words matching the prefix and the indices of words matching the suffix. Return the largest index present in both.

• Early termination: Return -1 immediately if either prefix or suffix trie search results in an empty list.

• Runtime Complexity: O(L*N) for the constructor, where L is the maximum length of a word and N is the number of words. O(P + S + M) for each query, where P and S are the lengths of prefix and suffix respectively, and M is the number of matching indices to find the maximum value. Storage Complexity: O(L*N), where L is the maximum length of a word and N is the number of words.

Code

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

class WordFilter:

    def __init__(self, words):
        self.prefix_trie = TrieNode()
        self.suffix_trie = TrieNode()

        for i, word in enumerate(words):
            self.insert_prefix(word, i)
            self.insert_suffix(word, i)

    def insert_prefix(self, word, index):
        node = self.prefix_trie
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.indices.append(index)

    def insert_suffix(self, word, index):
        node = self.suffix_trie
        for char in reversed(word):
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.indices.append(index)

    def search_prefix(self, pref):
        node = self.prefix_trie
        for char in pref:
            if char not in node.children:
                return []
            node = node.children[char]
        return node.indices

    def search_suffix(self, suff):
        node = self.suffix_trie
        for char in reversed(suff):
            if char not in node.children:
                return []
            node = node.children[char]
        return node.indices

    def f(self, pref, suff):
        prefix_indices = self.search_prefix(pref)
        suffix_indices = self.search_suffix(suff)

        if not prefix_indices or not suffix_indices:
            return -1

        i = len(prefix_indices) - 1
        j = len(suffix_indices) - 1
        max_index = -1

        while i >= 0 and j >= 0:
            if prefix_indices[i] == suffix_indices[j]:
                max_index = prefix_indices[i]
                break
            elif prefix_indices[i] > suffix_indices[j]:
                i -= 1
            else:
                j -= 1

        return max_index