[leetcode medium] 211. Design Add and Search Words Data Structure

(2) Design Add and Search Words Data Structure - LeetCode

Design Add and Search Words Data Structure - LeetCode

Constraints:

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of  '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

현재까지 들어온 문자열을 대상으로 일치하는 문자열이 있는지 반환하는 문제입니다.

 

두가지의 접근 방법이 있습니다.

 

• Trie 이용하기

1. 트리 생성

입력으로 들어오는 문자열을 대상으로 앞글자부터 차례대로 자식 노드를 생성하며 진행해 나갑니다.

현재 노드가 문자열의 마지막인 경우, IsEndOfWord를 True로 설정합니다.

 

2. 트리 조회

트리 조회 시, 입력되는 문자열은 "."(이하 와일드카드) 혹은 알파벳 소문자로 이루어집니다.

조회 함수 $$Search(String)$$는 재귀적으로 문자열의 각 문자를 앞에서부터 확인해나가며 진행하고, 다음의 3가지중

동작 중 하나를 시행합니다.

 

1 ) 현재 문자가 와일드 카드인 경우.

와일드 카드는 모든 문자로 치환될 수 있으므로, 현재 노드의 모든 자식 노드들을 대상으로 탐색을 진행할 필요가 있습니다. $$loop$$문을 돌리며 모든 자식 노드들에 대해 재귀적으로 Search(String[1:])함수를 호출합니다.

이 때, True가 리턴 된 경우 더이상 볼 필요가 없으므로 True를 Return합니다.

 

2 ) 현재 문자가 알파벳인 경우

만약 현재 노드의 자식 노드 중 해당 알파벳을 키값으로 하는 노드가 있다면, 해당 노드를 대상으로 Search(String[1:])함수를 호출하고, 그 결괏값을 Return합니다.

 

그러한 노드가 존재하지 않는다면, False를 Return합니다.

 

3 ) 현재 위치가 문자열의 마지막인경우

현재 위치가 문자열의 마지막이면서, 동시에 기존에 입력된 문자열의 마지막 지점이라면, 

그 문자열과 Search에서 입력받은 문자열은 동일하다고 할 수 있습니다.

Search(String)은 위의 두가지 조건의 만족 여부에 따라 True/False를 리턴합니다.

 

위의 세가지 단계를 거치며, 우리는 기존에 입력된 문자열 중 현재 입력된 문자열과 일치하는 것이 있는지 알 수 있습니다.

class WordDictionary(object):

    def __init__(self):
        self.child = dict() #자식 노드 dict생성
        self.end = False

    def addWord(self, word):
        cur = self

        for v in word:
            if v not in cur.child:
                cur.child[v] = WordDictionary()

            cur = cur.child[v]
        cur.end = True

    def search(self, word):
        cur = self

        if not word:
            return cur.end

        if word[0] == ".":
            for next_dict in cur.child.values():    #
                if next_dict.search(word[1:]):
                    return True

        elif word[0] in cur.child:
            return cur.child[word[0]].search(word[1:])

        return False

• HashMap Set 이용하기

Hash를 이용한 풀이는 상술한 것보다 더욱 간단합니다.

문자열의 길이는 최대 500까지 가능하므로, 501칸의 크기를 가지는 HashMap Array를 생성합니다

* HashArray[501] -> [Hash,Hash,Hash,....]

 

문자열 입력 시, 해당 문자열의 길이를 인덱스로 하는 Hash맵에 문자열을 삽입합니다.

이후 조회 시, 마찬가지로, 해당 문자열의 길이를 인덱스로 하는 Hash맵의 요소들을 하나하나 타깃 문자열과 대조해나가며 일치 여부를 검사합니다.

class WordDictionary(object):

    def __init__(self):
        self.dictionary = [set() for i in range(501)]   #최대 500개의 dict 생성 가능

    def addWord(self, word):
        self.dictionary[len(word)].add(word)

    def search(self, word):
        for element in self.dictionary[len(word)]:
            for idx in range(len(word)):
                if word[idx] != element[idx] and word[idx] != ".": break
                if idx == len(word) - 1:    return True
        return False