[LeetCode][Python3] 208. Implement Trie (Prefix Tree)
2019. 3. 30. 01:14 |
프로그래밍/LeetCode
Problem :
https://leetcode.com/problems/implement-trie-prefix-tree/
My Solution :
class TrieNode:
def __init__(self):
self.children = [None]*26
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for c in word:
idx = ord(c)-97
curr.children[idx] = curr.children[idx] or TrieNode()
curr = curr.children[idx]
curr.is_end = True
def search(self, word: str, is_startswith=False) -> bool:
curr = self.root
for c in word:
idx = ord(c)-97
curr = curr.children[idx]
if not curr:
return False
return is_startswith or curr.is_end
def startsWith(self, prefix: str) -> bool:
return self.search(prefix, True)
Comment :
위는 알파벳 소문자라는 제약이 있어서 크기 26짜리 list를 사용한 것이고, 아래는 아무 문자에 대응하기 위해 dictionary를 사용한 것.
My Solution 2 :
class TrieNode:
def __init__(self):
self.children = dict()
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for c in word:
curr = curr.children.setdefault(c, TrieNode())
curr.is_end = True
def search(self, word: str, is_startswith=False) -> bool:
curr = self.root
for c in word:
curr = curr.children.get(c)
if not curr:
return False
return is_startswith or curr.is_end
def startsWith(self, prefix: str) -> bool:
return self.search(prefix, True)
'프로그래밍 > LeetCode' 카테고리의 다른 글
| [LeetCode][Python3] 295. Find Median from Data Stream (0) | 2019.04.02 |
|---|---|
| [LeetCode][Python3] 236. Lowest Common Ancestor of a Binary Tree (0) | 2019.04.01 |
| [LeetCode][Python3] 207. Course Schedule (0) | 2019.03.31 |
| [LeetCode][Python3] 116. Populating Next Right Pointers in Each Node (0) | 2019.03.30 |
| [LeetCode][Python3] 239. Sliding Window Maximum (0) | 2019.03.29 |
| [LeetCode][Python3] 315. Count of Smaller Numbers After Self (0) | 2019.03.28 |
| [LeetCode][Python3] 395. Longest Substring with At Least K Repeating Characters (0) | 2019.03.28 |
| [LeetCode][Python3] 73. Set Matrix Zeroes (0) | 2019.03.27 |
최근에 달린 댓글 최근에 달린 댓글