Leetcode 745. Prefix and Suffix Search

Design a data structure that, given a list of words, returns the index of a word with a given prefix and suffix (return the largest index if multiple, or -1 if none). Because words are short (≤7) and there can be up to 10^4 words/queries, you must preprocess the dictionary to support fast prefix+suffix lookup (e.g., by indexing all prefix–suffix pairs or using a combined trie).