745.md

Prefix and Suffix Search

Description

link

---

Solution

• See Code

---

Code

Complexity T : O(mn) M : O(mn)

class WordFilter:

    def __init__(self, words: List[str]):
        self.weights = {}
        for weight, word in enumerate(words):
            for i in range(len(word) + 1):
                for j in range(len(word) + 1):
                    self.weights[word[:i] + '#' + word[j:]] = weight

    def f(self, prefix: str, suffix: str) -> int:
        return self.weights.get(prefix + '#' + suffix, -1)