Trie (in Python)

Trie

검색어 추천할 때 target 문자열에 해당하는 다른 모든 하위 문자열들을 빠르게 탐색할 수 있다는 장점이 있다.

실제 코테에서 많이 나오는 거 같진 않지만, 잊고 있다가 가끔 한번씩 등장함

🔑 키포인트

1. Trie 만들기

딕셔너리를 활용하면 depth를 추가해가며 한 글자씩 저장하기 용이하다.

테스트케이스로 ["cat", "cats", "dog", "dogs", "app", "apple", "application"]이 주어졌다면, 아래와 같이 저장하는 구조다:

{'a': {'p': {'p': {'*': 'app',
                   'l': {'e': {'*': 'apple'},
                         'i': {'c': {'a': {'t': {'i': {'o': {'n': {'*': 'application'}}}}}}}}}}},
 'c': {'a': {'t': {'*': 'cat', 's': {'*': 'cats'}}}},
 'd': {'o': {'g': {'*': 'dog', 's': {'*': 'dogs'}}}}}

마지막에는 '*' : 전체 단어로 저장하면, dfs 탐색의 종료 조건으로 유용하게 활용할 수 있다.

코드로 구현하면 아래와 같다:

trie = {}
for word in words:
    cur_root = trie
    for c in word:
        if c not in cur_root:
            cur_root[c] = {}
        cur_root = cur_root[c]
    cur_root['*'] = word  # 마지막

2. Search : target에 해당하는 모든 단어 찾기 (DFS 활용)

딕셔너리를 만들 때도 그랬듯, target 단어를 탐색할 때도 역시 하나 글자씩 타고 들어가면서 탐색하면 된다.

그러나 target의 모든 단어를 타고 들어갔다고 끝이 아니다. 목표는 가능한 모든 하위 단어 리스트를 뽑아내는 것이기 때문이다. target이 "app"이라면, ["app", "apple", "application"]이 나와야 할 것이다.

즉, 마지막 글자를 시작점으로 DFS 탐색을 시작하면, '*'이라는 끝을 만날 때까지 파고 들어가서 조건을 충족하는 단어들을 찾아나갈 수 있다.

def dfs(cur):
    for k, v in cur.items():
        if k == '*':
            res.append(v)
            continue
        dfs(v)

# Search DFS
res = []
cur_root = trie
for c in target:
    cur_root = cur_root[c]
dfs(cur_root)  # 하위 탐색

✔️ 전체 코드

from pprint import pprint

# tc
words = ["cat", "cats", "dog", "dogs", "app", "apple", "application"]
target = "app"  # output: ["app", "apple", "application"]

# build trie
trie = {}
for word in words:
    cur_root = trie
    for c in word:
        if c not in cur_root:
            cur_root[c] = {}
        cur_root = cur_root[c]
    cur_root['*'] = word

pprint(trie)
'''
{'a': {'p': {'p': {'*': 'app',
                   'l': {'e': {'*': 'apple'},
                         'i': {'c': {'a': {'t': {'i': {'o': {'n': {'*': 'application'}}}}}}}}}}},
 'c': {'a': {'t': {'*': 'cat', 's': {'*': 'cats'}}}},
 'd': {'o': {'g': {'*': 'dog', 's': {'*': 'dogs'}}}}}
'''


def dfs(cur):  # target에 대하여 가능한 모든 후보 리스트 (dfs search)
    for k, v in cur.items():
        if k == '*':
            res.append(v)
            continue
        dfs(v)


# search dfs
res = []
cur_root = trie
for c in target:
    cur_root = cur_root[c]
dfs(cur_root)  # 하위 탐색

print(res)

👉 추천 문제

search-suggestions-system

가사검색