osori · February 7, 2021 12:38 · Dec 2, 2017 · Dec 2, 2017 · Dec 2, 2017 · Dec 2, 2017
diff --git a/py_trie.py b/py_trie.py
@@ -7,47 +7,34 @@ def __init__(self):
     """
     def insert(self, string):
         curr_node = self.head
-        final_char = False;
-        data = string
 
-        for idx, c in enumerate(string):
-            if (idx == len(string)-1):
-                final_char = True
+        for char in string:
+            if char not in curr_node.children:
+                curr_node.children[char] = Node(char)
 
-            # 글자가 이미 트라이에 있는 경우
-            if c in curr_node.children:
-                curr_node = curr_node.children[c]
-
-            # 글자가 트라이에 존재하지 않음, 새 노드를 만든다.
-            else:
-                curr_node.children[c] = Node(c)
-                curr_node = curr_node.children[c]
+            curr_node = curr_node.children[char]
 
             # string 의 마지막 글자 차례이면,
             # 노드의 data 필드에 저장하려는 문자열 전체를 저장한다.
-            if (final_char):
-                curr_node.data = data
+        curr_node.data = string
 
 
     """
     주어진 단어 string이 트라이에 존재하는지 여부를 반환합니다.
     """
     def search(self, string):
         curr_node = self.head
-        final_char = False;
 
-        for idx, c in enumerate(string):
-            if (idx == len(string)-1):
-                final_char = True
-
-            if c in curr_node.children:
-                curr_node = curr_node.children[c]
-                # string의 마지막 글자에 다달았을 때,
-                # curr_node 에 data 가 있다면 string이 트라이에 존재하는 것!
-                if (final_char and curr_node.data != None):
-                    return True
+        for char in string:
+            if char in curr_node.children:
+                curr_node = curr_node.children[char]
             else:
                 return False
+
+        # string의 마지막 글자에 다달았을 때,
+        # curr_node 에 data 가 있다면 string이 트라이에 존재하는 것!
+        if (curr_node.data != None):
+            return True
 
     """
     주어진 prefix 로 시작하는 단어들을

diff --git a/py_trie.py b/py_trie.py
@@ -23,7 +23,7 @@ def insert(self, string):
                 curr_node.children[c] = Node(c)
                 curr_node = curr_node.children[c]
 
-            # 노드가 마지막 글자라면,
+            # string 의 마지막 글자 차례이면,
             # 노드의 data 필드에 저장하려는 문자열 전체를 저장한다.
             if (final_char):
                 curr_node.data = data

diff --git a/py_trie.py b/py_trie.py
@@ -48,7 +48,6 @@ def search(self, string):
                     return True
             else:
                 return False
-        return False
 
     """
     주어진 prefix 로 시작하는 단어들을

diff --git a/py_trie.py b/py_trie.py
@@ -3,7 +3,7 @@ def __init__(self):
         self.head = Node(None)
 
     """
-    Inserts a string in the trie.
+    트라이에 문자열을 삽입합니다.
     """
     def insert(self, string):
         curr_node = self.head
@@ -14,23 +14,23 @@ def insert(self, string):
             if (idx == len(string)-1):
                 final_char = True
 
-            # char already exists
+            # 글자가 이미 트라이에 있는 경우
             if c in curr_node.children:
                 curr_node = curr_node.children[c]
 
-            # char does not exist, create a new node for the char
+            # 글자가 트라이에 존재하지 않음, 새 노드를 만든다.
             else:
                 curr_node.children[c] = Node(c)
                 curr_node = curr_node.children[c]
 
-            # If the Node represents the final character of the string,
-            # set its data to the string.
+            # 노드가 마지막 글자라면,
+            # 노드의 data 필드에 저장하려는 문자열 전체를 저장한다.
             if (final_char):
                 curr_node.data = data
 
 
     """
-    Returns if the string exists in the trie
+    주어진 단어 string이 트라이에 존재하는지 여부를 반환합니다.
     """
     def search(self, string):
         curr_node = self.head
@@ -42,31 +42,34 @@ def search(self, string):
 
             if c in curr_node.children:
                 curr_node = curr_node.children[c]
-                # does the current node represent final character?
+                # string의 마지막 글자에 다달았을 때,
+                # curr_node 에 data 가 있다면 string이 트라이에 존재하는 것!
                 if (final_char and curr_node.data != None):
                     return True
             else:
                 return False
         return False
 
     """
-    Returns a list of words in the trie
-    that starts with the given prefix.
+    주어진 prefix 로 시작하는 단어들을
+    트라이에서 찾아 리스트 형태로 반환합니다.
     """
     def starts_with(self, prefix):
         curr_node = self.head
         result = []
         subtrie = None
 
-        # Locate the prefix in the trie
+        # 트라이에서 prefix 를 찾고,
+        # prefix의 마지막 글자 노드를 subtrie로 설정
         for char in prefix:
             if char in curr_node.children:
                 curr_node = curr_node.children[char]
                 subtrie = curr_node
             else:
                 return None
 
-        # If prefix exists, search for words in the prefix subtrie
+        # bfs 로 prefix subtrie를 순회하며 
+        # data가 있는 노드들(=완전한 단어)를 찾는다.
         queue = list(subtrie.children.values())
 
         while queue:

diff --git a/py_trie.py b/py_trie.py
@@ -0,0 +1,79 @@
+class Trie(object):
+    def __init__(self):
+        self.head = Node(None)
+
+    """
+    Inserts a string in the trie.
+    """
+    def insert(self, string):
+        curr_node = self.head
+        final_char = False;
+        data = string
+
+        for idx, c in enumerate(string):
+            if (idx == len(string)-1):
+                final_char = True
+
+            # char already exists
+            if c in curr_node.children:
+                curr_node = curr_node.children[c]
+
+            # char does not exist, create a new node for the char
+            else:
+                curr_node.children[c] = Node(c)
+                curr_node = curr_node.children[c]
+
+            # If the Node represents the final character of the string,
+            # set its data to the string.
+            if (final_char):
+                curr_node.data = data
+
+
+    """
+    Returns if the string exists in the trie
+    """
+    def search(self, string):
+        curr_node = self.head
+        final_char = False;
+
+        for idx, c in enumerate(string):
+            if (idx == len(string)-1):
+                final_char = True
+
+            if c in curr_node.children:
+                curr_node = curr_node.children[c]
+                # does the current node represent final character?
+                if (final_char and curr_node.data != None):
+                    return True
+            else:
+                return False
+        return False
+
+    """
+    Returns a list of words in the trie
+    that starts with the given prefix.
+    """
+    def starts_with(self, prefix):
+        curr_node = self.head
+        result = []
+        subtrie = None
+
+        # Locate the prefix in the trie
+        for char in prefix:
+            if char in curr_node.children:
+                curr_node = curr_node.children[char]
+                subtrie = curr_node
+            else:
+                return None
+
+        # If prefix exists, search for words in the prefix subtrie
+        queue = list(subtrie.children.values())
+
+        while queue:
+            curr = queue.pop()
+            if curr.data != None:
+                result.append(curr.data)
+
+            queue += list(curr.children.values())
+
+        return result
No results found