[leetcode]208. implement-trie-prefix-tree

📃문제 설명

문자열 탐색이 가능한 trie를 설계하면 된다. 입력한 문자열 전체 또는 입력 문자열로 시작하는 문자열의 존재 여부에 따라 True/False를 반환한다.

🖊 풀이 1

trie란 탐색 트리의 일종으로 비교적 빠른 문자 탐색이 가능하고,
공간 복잡도면에서도 효율적인 자료구조이다.
문자열의 각 문자를 노드로 가지며 리프 노드는 문자열 끝을 의미하는 prefix(접미사)를 넣어준다.

가장 먼저 생각해낸 방법은 리스트를 이용한 것 이다.
for문을 돌면서 리스트 안에 있는 데이터와 정확하게 일치하는 것을 찾을 수도 있고
내장 함수인 find를 이용하여 입력한 문자로 시작하는 문자열도 찾을 수 있다.

search의 시간 복잡도는 O(N) / startwith의 시간 복잡도는 O(NM) 이다.

🖊 풀이 2

탐색을 조금 더 효율적으로 하기 위해 dict를 이용해보았다.

우선 insert와 startwith의 차이는 문자열을 끝까지 순회하냐 아니냐의 차이이다.
insert에서는 문자열을 모두 돌았다는 의미에서 *를 만나면 True를 반환한다.
startwith은 for문을 돌면서 문자의 존재 여부를 확인한다.

search, startwith의 시간 복잡도는 모두 O(N)이다.