LeetCode 211. Design Add and Search Words Data Structure (python)

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.

 

 

풀이  

 

단어를 추가하고 이전에 추가된 문자열과 일치하는지 확인할 수 있는 데이터 구조를 설계하는 문제

문자열에서 '.'  마침표는 모든 문자와 일치할 수 있다.

 

 

TrieTree를 통해 문자열을 넣어주면 되는데 문자열에서 마침표 일 때 탐색을 어떻게해줘야할지 고민을 했다.

 

1.while문으로 모든 문자열 하위를 모두 탐색하기,

2.DFS로 다음 문자열이 동일한지 확인해서 탐색하기

 

DRF로 문자열 하위를 확인해서 재귀로 찾는법을 사용하기로했다.

 

class Node: # 해시맵으로 문자열이 들어갈 노드 작성
    def __init__(self):
        self.children={}
        self.endof =False	#문자열의 끝 확인 플래그 


class WordDictionary(object):

    def __init__(self):
        self.root = Node()	#root 최초시작 노드 자동생성,

        

    def addWord(self, word):
        node = self.root	# 첫 노드는 root로 시작,
        for i in word:
            if i not in node.children:	#node의 자식중 문자열 i가 없다면, 해당인덱스 노드생성
                node.children[i] = Node() 
            node= node.children[i]	#존재한다면 node는 해시맵[i]
        node.endof =1   # 완성문자열	# for문 종료 후 (문자 삽입 완료) 해당 노드 endof로 완성플래그 
        
    def dictFind(self,node,word):
        if not word: # 마지막 도달 종료 조건 node가 존재하지 않을때 종료된 곳이 endof가 True인지 확인, 
            if node.endof:
                self.result = True  #endof가 True라면 result= True로 변경 
            return 
        if  word[0] == '.': # 마침표가 들어왔을때, 현재 노드의 모든 해시맵 탐색,
            for i in node.children.values():	# for문을 통해서 dictFind함수재귀로 탐색
                self.dictFind(i,word[1:])
        else:
            node = node.children.get(word[0])	#문자열의 첫번째 인덱스가, 현재 노드의 해시맵에 존재하는지 탐색
            if not node:	# 존재 하지 않는다면 종료 
                return
            self.dictFind(node,word[1:])	 #슬라이싱을 통해 2번쨰 인덱스부터 끝 인덱스 word로 재귀탐색



    def search(self, word):
        node = self.root 	# 첫시작 노드 설정
        self.result = False	#result 디폴트 설정 False
        self.dictFind(node,word) # dictFind를 통해 탐색시작 (재귀탐색)
        return self.result	#탐색 종료후 result 리턴 
        

        """
        :type word: str
        :rtype: bool
        """
    


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

마침표가  나왔을 때 for문을 통해서 현재 노드의 모든 하위 문자열을 for문으로 순회하며  dictFind 로 깊이 탐색을 시행한다.

 

외에는 재귀를 통해 하위 문자열로 연결,

 

 

다른사람의코드

 

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

class WordDictionary:

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

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def search(self, word: str) -> bool:
        nodes = [self.root]
        for ch in word:
            next_nodes = []
            for node in nodes:
                if ch in node.children:
                    next_nodes.append(node.children[ch])
                if ch == '.':
                    next_nodes.extend(node.children.values())
            nodes = next_nodes
        
        for node in nodes:
            if node.is_word:
                return True
        
        return False

리스트를 사용해 탐색을 진행한다,  search의 함수에서 nodes에 담긴 node들을 모두 탐색하며 bfs로 각 노드들을 탐색하여 마지막에 도달하지는지 확인한다 . extend함수를 사용하여 '.' 일때 현재 인덱스의 모든 노드들을 next_nodes에 담아서 반복적으로 탐색을 수행하고, 모든 탐색이 끝났을때 맨 마지막 노드에서 완성된 문자열인지 확인한다.