[파이썬 알고리즘 인터뷰][트라이] 트라이 구현

[파이썬 알고리즘 인터뷰][트라이] 트라이 구현

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

문제 정의

트라이 구현하기

책에서 구현된 코드

import collections # 트라이의 노드 class TrieNode: def __init__(self): self.word = False self.children = collections.defaultdict(TrieNode) class Trie: def __init__(self): self.root = TrieNode() # 단어 삽입 def insert(self, word: str) -> None: node = self.root for char in word: node = node.children[char] node.word = True # 단어 존재 여부 판별 def search(self, word: str) -> bool: node = self.root for char in word: if char not in node.children: return False node = node.children[char] return node.word # 문자열로 시작 단어 존재 여부 판별 def startsWith(self, prefix: str) -> bool: node = self.root for char in prefix: if char not in node.children: return False node = node.children[char] return True

기억해야할 기법

Class로 선언한 객체 사용

트라이에 문자 확인 외에 기능이 필요할 경우, 책에서 구현한 방법과 같이 TrieNode를 선언하여 이용

내가 구현한 코드

class Trie: word = "word" def __init__(self): self.trie = dict() def insert(self, word: str) -> None: trie = self.trie for c in word: if c not in trie: trie[c] = dict() trie = trie[c] trie[self.word] = True def search(self, word: str) -> bool: trie = self.trie for c in word: if c not in trie: return False trie = trie[c] return self.word in trie def startsWith(self, prefix: str) -> bool: trie = self.trie for c in prefix: if c not in trie: return False trie = trie[c] return True

나는 trie 딕셔너리에 담길 key가 char(길이 1인 string)임을 이용

word의 경우 길이 2 이상의 string key "word"를 담아 search에서 "word" key를 확인

Class 생성이 없어서 그런지 속도와 메모리 면에서 책에서 구현한 알고리즘보다 좋음

그러나 현업에서 이런 방식으로 개발하면 큰일날듯...

from http://pythaac.tistory.com/131 by ccl(A) rewrite - 2021-08-05 15:00:27