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

• 트라이: 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조
  • 특히 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다
  • 검색을 뜻하는 'retrieval'에서 따옴
  • 다진 트리의 형태
  • 각 문자열 길이만큼만 탐색하면 원하는 결과 찾을 수 있다

208. Implement Trie (Prefix Tree)

- TrieNode 클래스 생성해 딕셔너리로 노드 값 정보, 불리안으로 해당 노드에서 단어 완성 여부 정보를 각 노드에 담는다

-> 삽입이나 검색하려는 문자열 갯수만큼 반복하여 각 노드의 딕셔너리 확인하며 필요한 작업 수행

 

336. Palindrome Pairs

- 부르트 포스 -> 시간 초과 O(n^2)

- 트라이 구현 -> 입력값 철자 역순으로 트라이 구성하고 탐색은 순서대로 -> 탐색이 진행된다 = 그 철자까지 팰린드롬

검은색: 입력값

1. 끝까지 탐색했을 때 word_id 값 있는 경우

2. 끝까지 탐색했을 때 palindrome_word_ids 값 있는 경우

3. 탐색 중간에 word_id 값 있고, 입력값 기준 나머지 철자들이 팰린드롬인 경우

• @staticmethod 데코레이터로 정의된 메소드는 클래스와 독립적인 함수로서 의미를 강하게 갖는다
• 사실상 클래스 바깥에 함수를 별도 선언한 것과 같아 클래스 메소드처럼 자유롭게 클래스 인스턴스 접근 제한