[HackerRank][Python3] Tries: Contacts

Problem :

https://www.hackerrank.com/challenges/ctci-contacts/problem

My Solution :

#!/usr/bin/env python3


class Node(object):
    def __init__(self):
        self.children = {}
        self.count = 0


class Trie(object):
    def __init__(self):
        self.head = Node()

    def add(self, data):
        curr = self.head
        for c in data:
            curr = curr.children.setdefault(c, Node())
            curr.count += 1

    def find(self, data):
        curr = self.head
        for c in data:
            if c not in curr.children:
                return 0
            curr = curr.children[c]
        return curr.count


n = int(input())
trie = Trie()
for _ in range(n):
    op, contact = input().split()
    if op == 'add':
        trie.add(contact)
    else:
        print(trie.find(contact))

My Solution2 :

아래는 위처럼 직접 class를 설계하지 않고, 기본 dictionary 자료구조를 활용한 버전이다.

#!/usr/bin/env python3


def add_contact(trie, contact):
    curr = trie
    for c in contact:
        curr = curr.setdefault(c, {})
        curr['count'] = curr.setdefault('count', 0) + 1


def find_contact(trie, contact):
    curr = trie
    for c in contact:
        if c not in curr:
            return 0
        curr = curr[c]
    return curr['count']


n = int(input())
trie = {}
for _ in range(n):
    op, contact = input().split()
    if op == 'add':
        add_contact(trie, contact)
    else:
        print(find_contact(trie, contact))

My Solution3 :

이번에는 dictionary 대신 크기 27짜리 list를 활용해 보았다. 입력은 소문자이기 때문에 26개 칸은 소문자 - 97을 Index로 사용하고, 마지막 칸에는 count를 저장하였다.

#!/usr/bin/env python3


def add_contact(trie, contact):
    curr = trie
    for c in contact:
        pos = ord(c)-97
        if not curr[pos]:
            curr[pos] = [0]*27
        curr = curr[pos]
        curr[26] += 1


def find_contact(trie, contact):
    curr = trie
    for c in contact:
        pos = ord(c)-97
        if not curr[pos]:
            return 0
        curr = curr[pos]
    return curr[26]


n = int(input())
trie = [0]*27
for _ in range(n):
    op, contact = input().split()
    if op == 'add':
        add_contact(trie, contact)
    else:
        print(find_contact(trie, contact))