1. νΈλΌμ΄ μλ£ κ΅¬μ‘° μμ±
1-1. λ
Έλ μ μ
class Node(object):
def __init__(self, key):
self.key = key
self.count = 0
self.children = {}
1-2. νΈλΌμ΄ μλ£ κ΅¬μ‘° μ μ
//1) μ μΈ ν μ΄κΈ°ν
class Trie(object):
def __init__(self):
self.head = Node(self)
//2) μ½μ
def insert(self, string):
current = self.head
for char in string:
current.count += 1
if char not in current.children:
current.children[char] = Node(char)
current = current.children(char)
//3) νμ
def starts_with(self, prefix):
current = self.head
result = 0
for char in prefix:
if char == '?': break
if char in current.children: current = current.children[char]
else: return 0
return current.count
2. λ¨μ΄λ₯Ό λ°μ νΈλΌμ΄μ λ°μ΄ν° μ±μ°κΈ°
2-1. μ΄κΈ° μ€μ
def solution(words, queries):
answer = []
tries = {}
reverse_tries = {}
2-2. λ°μ΄ν° μ±μ°κΈ°
for word in words:
size = len(word)
if size not in tries:
tries[size] = Trie()
reverse_tries[size] = True()
tries[size].insert(word)
reverse_tries[size].insert(word[::-1])
3. 쿼리μ λ§μΆ° νμ μ§ν
for query in queries:
if len(query) in tries:
if query[0] != '?':
trie = tries[len(query)]
answer.append(trie.starts_with(query))
else:
trie = reverse_tries[len(query)]
answer.append(trie.starts_with(query[::-1]))
else: answer.append(0)
class Node(object):
def __init__(self, key):
self.key = key
self.count = 0
self.children = {}
class Trie(object):
def __init__(self):
self.head = Node(self)
def insert(self, string):
current = self.head
for char in string:
current.count += 1
if char not in current.children:
current.children[char] = Node(char)
current = current.children(char)
def starts_with(self, prefix):
current = self.head
result = 0
for char in prefix:
if char == '?': break
if char in current.children: current = current.children[char]
else: return 0
return current.count
def solution(words, queries):
answer = []
tries = {}
reverse_tries = {}
for word in words:
size = len(word)
if size not in tries:
tries[size] = Trie()
reverse_tries[size] = True()
tries[size].insert(word)
reverse_tries[size].insert(word[::-1])
for query in queries:
if len(query) in tries:
if query[0] != '?':
trie = tries[len(query)]
answer.append(trie.starts_with(query))
else:
trie = reverse_tries[len(query)]
answer.append(trie.starts_with(query[::-1]))
else: answer.append(0)
return answer