[hard] 745. Prefix and Suffix Search

문제

https://leetcode.com/problems/prefix-and-suffix-search/description/

---

풀이방법

처음에는 단순하게 리스트에서 문자열 비교 방법을 사용했는데, 역시나 시간초과.
두번째로는 아래의 힌트를 참고해서 단어 이어붙인 다음, 문자열 비교하는 방법을 사용했는데 이것도 역시 시간초과.

힌트

For a word like "test", consider "#test", "t#test", "st#test", "est#test", "test#test". Then if we have a query like prefix = "te", suffix = "t", we can find it by searching for something we've inserted starting with "t#te".

세번째로는 두번째처럼 단어를 이어붙이는건 맞는데, 이걸 trie 구조로 만들면 시간초과 문제가 해결됨.
예를들어 "test"의 경우, 단어를 이어붙일 때 위의 힌트와 같은 경우의 수가 나올 수 있는데
이걸 trie로 구성하면 아래 그림과 같이 구성되어서 탐색에 걸리는 시간을 절약할 수 있다.

반응형

---

코드

### 첫번째 아이디어: 단순한 문자열 비교 방법 -> 시간초과 ###
class WordFilter:
    def __init__(self, words: List[str]):
        self.words = words
        
    def f(self, prefix: str, suffix: str) -> int:
        ret = -1
        lp = len(prefix)
        ls = len(suffix)
        for idx, word in enumerate(reversed(self.words)):
            if word[:lp] == prefix and word[-ls:] == suffix:
                ret = len(self.words)-idx-1
                break
        return ret

### 두번째 아이디어: 힌트 보고 word+"#"+word 를 활용해서 문자열 검색하는 방법 ###
class WordFilter:
    def __init__(self, words: List[str]):
        self.words = {}
        for idx, word in enumerate(words):
            self.words[word+"#"+word] = idx
                
    def f(self, prefix: str, suffix: str) -> int:
        ret = -1
        for word in reversed(self.words.keys()):
            if suffix+"#"+prefix in word:
                ret = self.words[word]
                break
        return ret

### 세번째 아이디어: trie 구조로 변경 ###
class TrieNode:
    def __init__(self):
        self.children = {}
        self.index = -1

class WordFilter:
    def __init__(self, words: List[str]):
        self.root = TrieNode()
        
        for idx, word in enumerate(words):
            lenword = len(word)
            word = word+"#"+word
            for wi in range(lenword):
                newword = word[wi:]
                node = self.root
                for c in newword:
                    if c not in node.children:
                        node.children[c] = TrieNode()
                    node = node.children[c]
                    node.index = idx
                    
    def f(self, prefix: str, suffix: str) -> int:
        ret = -1
        word = suffix+"#"+prefix
        node = self.root
        for c in word:
            if c not in node.children:
                ret = -1
                break
            node = node.children[c]
            ret = node.index
        return ret