Design Add and Search Words Data Structure

문제

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

풀이

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

wordDict를 생성하고 bad, dad, mad를 추가한다. 그다음 pad를 찾으면 저장되지 않았으므로 False, bad는 존재하므로 True, .는 와일드카드로 문자가 지정되지 않은 경우이다. 나머지 글자가 매칭되므로 True를 리턴한다.

수도 코드

class Node:
	t = 자신 밑의 children, 딕셔너리
    is_word = False
    
class WordDictionary(object):

    def __init__(self):
        root = Node()

    def addWord(self, word):
        curr = root부터
        for word 한 글자씩:
        	curr = curr의 t를 c: Node()로 지정
        word의 마지막을 가리키는 curr의 is_word를 True로 변경
        

    def search(self, word):
        def dfs탐색(현재 노드, word의 현재 인덱스값):
        	if word의 현재 인덱스값이 len(word)이라면:
            	return node의 is_word 
            
            if word[인덱스] == '.':
            	for c in 현재노드의 자식트리.value():
                	if dfs(c, 인덱스값 + 1)이 참이라면:
                    	return True
            if word[인덱스] in node의 자식트리:
            	return dfs(node의 자식트리[word[인덱스]], pos + 1)
            return False # 여기까지 도달했다면 찾을 수 없는 경우임
      	return dfs

Solution(Runtime: 2156ms)

class Node:
    def __init__(self):
        self.t = {}
        self.is_word = False

class WordDictionary(object):

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

    def addWord(self, word):
        curr = self.root
        for c in word:
            curr = curr.t.setdefault(c, Node())
        curr.is_word = True
        

    def search(self, word):
        n = len(word)
        def dfs(node, pos=0):
            if pos == n:
                return node.is_word
            
            if word[pos] == '.':
                for c in node.t.values():
                    if dfs(c, pos + 1):
                        return True
            
            if word[pos] in node.t:
                return dfs(node.t[word[pos]], pos + 1)
            
            return False

        return dfs(self.root)

파이썬3로 제출했더니 엄청난 시간이 소요되었다. Beats 74.18%of users with Python3 인거보면 어쩔 수 없는 것 같다.

이 문제에서 가장 중요한 부분은 search 메서드 구현이라고 생각한다. "aaa"라는 값이 트라이에 저장되어 있고 "aaa."의 쿼리가 존재한다고 가정할 때, False를 반환해야 한다. 기존의 트라이 구현으로는 .의 처리와 저장된 값보다 더 큰 길이를 검색하려할 때 문제가 발생한다. 따라서 트라이의 각 노드를 클래스로 생성하고 is_word 값으로 맞는 값인지 나타내주었다.