[Leetcode] 1032. Stream of Characters

21-12-04
Solved in a poor way.

Problem

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.

For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.

Implement the StreamChecker class:

StreamChecker(String[] words) Initializes the object with the strings array words.
boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.

character stream에서 char 하나를 받으면서 단어를 형성한다고 할 때, 해당 char를 마지막으로 하는 단어에서, word 안에 surfix를 가지고 있는가를 확인해주는 알고리즘이다.

Poor Solution

class Node:
    def __init__(self,val=None):
        self.val=val
        self.child={}

class Trie:
    def __init__(self):
        self.head=Node()
    
    def insert(self,chars):
        cur=self.head
        
        for char in chars:
            if char not in cur.child:
                cur.child[char]=Node(char)
            cur=cur.child[char]
        cur.child['*']=Node('*')
    
    def search(self,chars):
        cur=self.head
        
        for char in chars:
            if char not in cur.child:
                return False
            cur=cur.child[char]
        if '*' in cur.child:
            return True
            
    def nextNode(self,node,ch):
        if ch not in node.child:
            return None
        
        node=node.child[ch]
        return node
        
        
class StreamChecker:
    
    def __init__(self, words: List[str]):
        self.trie=Trie()
        for word in words:
            self.trie.insert(word)
        self.cands=[]

    def query(self, letter: str) -> bool:
        ans=False
        tmp=[]
        for cand in self.cands:
            if letter not in cand.child:
                continue
            trav= cand.child[letter]
            if '*' in trav.child:
                ans=True
            tmp.append(trav)
        
        if letter in self.trie.head.child:   
            cur= self.trie.head.child[letter]
            if '*' in cur.child:
                ans=True
            tmp.append(cur)
        
        self.cands=tmp
        
        return ans

처음에 word를 trie에 저장을 한다. 그리고 stream을 한 글자씩 받아들인다. 그리고 그 글자를 cands에 넣어 가능한 surfix가 있을 때까지 trie에서 next Node를 찾게한다.
trie는 처음 구현해보기 때문에 다음을 참고했다.

하지만 가능한 모든 상황을 하나하나 검토하기 때문에 시간이 너무 오래 걸린다. 아래 Best Solution과 비교해서 봐야한다. 내 풀이는 i 번째 스트림을 읽어올 때, 이미 그전에 읽어들였던 스트림 character를 대상으로 만들 수 있는 surfix를 traverse한다. 따라서 문자 하나를 볼 때도, cand이라는 리스트를 통해 surfix 후보를 여러개 두개 된다. 그래서 testcase 통과도 아슬아슬하게 했다. (처음 Trie의 메소드, nextNode를 호출해서 하다가 시간이 너무 길어져서, 쓰지 않게 고쳤더니 통과했다.) 하지만 아래의 풀이는 문자 하나 당 여러개의 후보를 두는게아니라, surfix를 거꾸로 저장해두고, streame도 거꾸로 읽어서 해당 문자에 가능한 surfix만 특정해서 찾게 된다.

Best Solution

class TrieNode():
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie():
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True

class StreamChecker:
    def __init__(self, words: List[str]):
        self.letters = []
        self.trie = Trie()
        for w in words:
            self.trie.insert(w[::-1])
        
    def query(self, letter: str) -> bool:
        self.letters.append(letter)
        i = len(self.letters) - 1
        node = self.trie.root
        while i >= 0:
            if node.isEnd:
                return True
            if self.letters[i] not in node.children:
                return False
            node = node.children[self.letters[i]]
            i -= 1
        return node.isEnd

우선 trie에 단어를 역순(w[::-1])으로 저장한다. 그리고 문자를 하나 읽을 때마다, letter에 저장을 해둔다. letter하나당 letters를 거꾸로 indexing하면서 trie의 child로 traversing한다. 이렇게 하면, 내가 solution에서 한 것과는 다르게, 거꾸로 surfix를 만들어서 모든 상황이 아닌 확실하게 가능한 상황만 고려하게 된다. 그래서 시간이 단축된다.
또한 trie를 다른 방식으로 구현했다. 이 문제에서는 Node에 value를 가질 필요가 없어서 넣지 않았다. 그리고 isEnd라는 Flag로 대체했다.

Simple Solution

class StreamChecker:

    def __init__(self, words: List[str]):
        self.stream = deque([])
        self.trie = {}
        
        for word in set(words):
            node = self.trie
            for c in word[::-1]:
                if c not in node:
                    node[c] = {}
                node = node[c]
            node['$'] = word
            
    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        node = self.trie
        for c in self.stream:
            if '$' in node:
                return True
            if c not in node:
                return False
            node = node[c]
        return '$' in node

시간 복잡도가 좋은 solution example을 가져왔다. 굳이 trie를 따로 class로 구현하지 않은 모습이다. 그리고 indexing을 거꾸로하는 것이 아니라, deque를 사용해 저장해둔 stream을 정방향으로 읽게 했다.