-
Notifications
You must be signed in to change notification settings - Fork 0
Trie
Bong edited this page Mar 8, 2021
·
7 revisions
- HashMap(
dict
in python)을 활용해서 만든 트리- 여러 단어들을 하나의 트리에 넣어서, prefix/whole word 처리를 할 때 유용하다.
- Trie 구조 생성 복잡도
O(L*N)
(L
: 문자열 최대 길이,N
: 문자열 총 개수)
- Trie 구조 생성 복잡도
- 여러 단어들을 하나의 트리에 넣어서, prefix/whole word 처리를 할 때 유용하다.
어려운 문제가 아닌 경우, Trie 를 따로 만들지 않고 set
또는 dict
을 사용해도 풀린다.
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에 포함된 전체 단어들에 대해서 한꺼번에 재귀로 계산할 수 있는가? (풀긴 풀었는데 코드를 다시 한번 생각)
주어진 단어들을 최대한 함축해서 표현하는 문제.
입력: words = ["time", "me", "bell"]
출력: 10
설명: "me"가 "time"의 postfix에 포함되므로, "time#bell#" 으로 표현할 수 있다.
postfix가 겹치는 단어는 지워질 수 있으므로, 모든 단어들을 뒤집어서 Trie 구조에 집어넣으면 된다. 모든 단어들을 넣은 다음, Trie의 root node부터 각 leaf node까지의 길이(단어 길이)를 모두 더하고, leaf node의 총 개수(# 개수)를 더해주면 된다.