가사검색 문제와 비슷함. Trie Tree 를 이용한 문제
def solution(words):
tree = Trie()
for word in words :
tree.insert(word)
return sum(tree.query(word) for word in words)
class TrieNode:
def __init__(self, char):
self.char = char
self.counter = 0
self.children = {}
class Trie(object):
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for char in word:
node.counter += 1
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.counter += 1
def query(self, word) :
node = self.root
for i, char in enumerate(word) :
node = node.children[char]
if node.counter == 1 :
return i+1
return len(word)
알고리즘
words를Trie Tree에 삽입한 후, 공통 단어를 가지지않는 부분까지word의 길이를 구한다.
각 단어 타고 내려가면서
counter == 1이 나오는 단어의 길이return
counter == 1이 없다면 끝까지 단어를 쳐야하는 경우이므로 단어의 길이return
def solution(words):
tree = Trie()
for word in words :
tree.insert(word)
return sum(tree.query(word) for word in words)
class TrieNode:
def __init__(self, char):
self.char = char
self.counter = 0
self.children = {}
class Trie(object):
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for char in word:
node.counter += 1
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.counter += 1
def query(self, word) :
node = self.root
for i, char in enumerate(word) :
node = node.children[char]
if node.counter == 1 :
return i+1
return len(word)