Trie

Trie 자료 구조

• HashMap(dict in python)을 활용해서 만든 트리
  • 여러 단어들을 하나의 트리에 넣어서, prefix/whole word 처리를 할 때 유용하다.
    • Trie 구조 생성 복잡도 O(L*N)(L: 문자열 최대 길이, N: 문자열 총 개수)

관련 문제들

어려운 문제가 아닌 경우, Trie 를 따로 만들지 않고 set 또는 dict 을 사용해도 풀린다.

1. 전화번호 목록, 개미굴

2. 가사 검색

* 매칭 시, Trie 활용 팁 두가지
    1. 각 Trie node에 `length` 변수 추가 후 Trie 구축중에 계산 (`length`: 해당 노드 이후 매칭되는 단어의 총 개수)
    2. prefix 단어(e.g. `???ord`) matching 에는 단어를 거꾸로 해서 넣은 Trie 사용, 
    postfix 단어(e.g. `ord???`) matching 에는 일반 Trie 사용
    3. 만약 매칭해야되는 단어의 길이가 다양할 경우, 길이에 따른 여러개의 Trie를 구성하는 것이 좋다.

3. 휴대폰 자판

* Trie에 포함된 전체 단어들에 대해서 한꺼번에 재귀로 계산할 수 있는가? (풀긴 풀었는데 코드를 다시 한번 생각)

4.Short Encoding of Words

주어진 단어들을 최대한 함축해서 표현하는 문제.

예시

입력: words = ["time", "me", "bell"]
출력: 10
설명: "me"가 "time"의 postfix에 포함되므로, "time#bell#" 으로 표현할 수 있다.

Solution of (4)

postfix가 겹치는 단어는 지워질 수 있으므로, 모든 단어들을 뒤집어서 Trie 구조에 집어넣으면 된다. 모든 단어들을 넣은 다음, Trie의 root node부터 각 leaf node까지의 길이(단어 길이)를 모두 더하고, leaf node의 총 개수(# 개수)를 더해주면 된다.