[Leetcode Hard] 745. Prefix and Suffix Search

Design a special dictionary with some words that searchs 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 prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. 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 <= 15000
• 1 <= words[i].length <= 10
• 1 <= prefix.length, suffix.length <= 10
• words[i], prefix and suffix consist of lower-case English letters only.
• At most 15000 calls will be made to the function f.

word를 word의 suffix + { + word (최대 10가지 경우의 수) 형태의 문자열로 만들어 전체 Trie를 구성하고,

이후 각 쿼리에서 들어온 prefix와 suffix에 대해, 타깃 문자열을 suffix + { + prefix 로 만들어 Trie를 순회하는 식으로 구현하였습니다.

 

from typing import List


class Node:
    def __init__(self):
        self.child = [None] * 27  # 26 alphabet / 1 {
        self.value = -1


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str, index: int) -> None:
        node = self.root

        for spell in word:
            child = ord(spell) - ord("a")

            if not node.child[child]:
                node.child[child] = Node()

            node = node.child[child]
            node.value = index

    def search(self, word: str) -> int:
        node = self.root
        for spell in word:
            child = ord(spell) - ord("a")

            if not node.child[child]:
                return -1

            node = node.child[child]
        return node.value


class WordFilter:

    def __init__(self, words: List[str]):
        self.FilterTree = Trie()

        for index, word in enumerate(words):
            for i in range(1, min(11, len(word) + 1)):
                # 1 ~ 11개까지
                self.FilterTree.insert(word=word[-i:] + "{" + word[:min(len(word), 11)], index=index)

    def f(self, prefix: str, suffix: str) -> int:
        return self.FilterTree.search(suffix + "{" + prefix)

    # Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)