Prefix and Suffix Search

class PrefixSuffixFilter {
    TrieNode root;
    public PrefixSuffixFilter(String[] words) {
        root = new TrieNode();
        for (int index = 0; index < words.length; index++) {
            String modifiedWord = words[index] + "{";
            for (int i = 0; i < modifiedWord.length(); i++) {
                TrieNode node = root;
                node.weight = index;
                for (int j = i; j < 2 * modifiedWord.length() - 1; j++) {
                    int charIndex = modifiedWord.charAt(j % modifiedWord.length()) - 'a';
                    if (node.branches[charIndex] == null) {
                        node.branches[charIndex] = new TrieNode();
                    }
                    node = node.branches[charIndex];
                    node.weight = index;
                }
            }
        }
    }
    public int search(String pref, String suff) {
        TrieNode node = root;
        for (char ch: (suff + '{' + pref).toCharArray()) {
            if (node.branches[ch - 'a'] == null) {
                return -1;
            }
            node = node.branches[ch - 'a'];
        }
        return node.weight;
    }
}

class TrieNode {
    TrieNode[] branches;
    int weight;
    public TrieNode() {
        branches = new TrieNode[27];
        weight = 0;
    }
}

The provided Java solution focuses on building a robust system for filtering words based on both prefix and suffix using a custom Trie (prefix tree) data structure. The system is suitable to address efficient searching which is critical in applications such as autocomplete features and spell-checkers.

• The key elements of the solution involve the PrefixSuffixFilter and TrieNode classes.

• In the PrefixSuffixFilter class:

  • A TrieNode named root is instantiated to serve as the starting point of the trie.
  • The constructor takes an array of words and processes each word by appending a special character { to help distinguish between the end of a suffix and the start of a prefix in the trie.
  • Each word is then iteratively added to the trie in a way that every possible suffix-prefix combination of the word is preserved as a unique path in the trie, indexed by the position of the word in the original array to facilitate fast lookups.

• The search method allows checking the highest index of words that contain a given prefix after a given suffix. This is done by:

  • Concatenating the suffix with the { character and the prefix, forming a single string which represents a potential path in the trie.
  • Navigating through the trie according to this path and returning the stored index which represents the most recent addition of a word that matches the prefix and suffix criteria.

• The TrieNode class is structured as:

  • An array of TrieNode references named branches, sized to accommodate the English lowercase letters and the special character {.
  • An integer weight that holds the index of the last word added along this path in the trie.

This design ensures that the search operation is performed in a time-efficient manner, since each query operates directly through the trie structure without the need for scanning or matching operations on the list of words. The trie effectively pre-processes and stores the data in a way that anticipates and optimizes for the search use case, making the search operation quick and scalable.

CreateTrie = lambda: collections.defaultdict(CreateTrie)
MAX_WEIGHT = False

class PrefixSuffixSearch:
    def __init__(self, words: List[str]):
        self.root = CreateTrie()

        for index, word in enumerate(words):
            modified_word = word + '#'
            for pos in range(len(modified_word)):
                node = self.root
                node[MAX_WEIGHT] = index
                for offset in range(pos, 2 * len(modified_word) - 1):
                    node = node[modified_word[offset % len(modified_word)]]
                    node[MAX_WEIGHT] = index

    def search(self, prefix: str, suffix: str) -> int:
        node = self.root
        for char in suffix + '#' + prefix:
            if char not in node:
                return -1
            node = node[char]
        return node[MAX_WEIGHT]

This Python solution focuses on implementing the PrefixSuffixSearch class to handle search queries that combine both a given prefix and a suffix in a list of words. The key data structure used here is a modified Trie (prefix tree).

• First, a Trie is created using a lambda function that recursively uses collections.defaultdict to instantiate new Tries, ensuring that every node in the Trie can dynamically create new child nodes if they do not already exist.
• The MAX_WEIGHT constant is used as a key in the Trie to store the maximum index of words that have been processed, facilitating the return of the most recent addition that matches the search criteria.

Detailed Steps in the Code:

1. Initialization (__init__ method):

   • Initializes the Trie.
   • Iterates through each word, modifying it by appending a '#' to help distinguish between the end of a suffix and the start of a prefix.
   • Inserts each possible combination of prefixes and suffixes of the word into the Trie. This includes rotating through the modified word and adding each rotation to the Trie, updating the maximum index each time.

2. Search Method:

   • Searches for the concatenation of the suffix, '#' and the prefix in the Trie.
   • If any character in this combined string is missing from the Trie during the traversal, it returns -1 indicating the combined prefix and suffix is not found.
   • If the traversal is successful, returns the stored MAX_WEIGHT at the terminal node, which represents the highest index of a word in the initial list that matches the search criteria.

This method ensures efficient querying, as it preprocesses the words to allow rapid searches for any given combination of prefix and suffix. This preprocessing step helps in reducing the complexity during the actual search, making the query operation faster especially beneficial when there are multiple queries to be performed on an infrequently changed list of words. The use of a Trie particularly aids in optimizing the space used, as common prefixes and suffixes are stored only once.