https://school.programmers.co.kr/learn/courses/30/lessons/17685

위 문제를 풀던 중 트라이 자료구조에 대해서 알게되었다

트라이를 포함한 문자열 검색 알고리즘 Trie, KMP, Rabin-Krap 에 대해서 알아보겠다

Trie

• 문자열의 집합을 표현하는 트리 자료구조의 일종이다
• 트리의 노드에 map을 저장하고, map에는 자식 노드들의 key를 저장한다
• 자동 검색어 완성, 사전 찾기, 문자열 검사 등에 사용한다

시간복잡도

N ⇒ 문자열 길이

• 삽입 : O(N)
• 검색 : O(N)
• 삭제 : O(N)

특징

• 장점 : 문자열을 빠르게 조회할 수 있다 ⇒ O(N)
• 단점 : 메모리 크기가 크다

구현

먼저 Node 클래스를 생성했다

Node에는 자식 노드를 저장하는 포인터 역할을 하는 child,

마지막 글자인지를 알려주는 boolean 변수 isLast가 있다

Trie에는 insert, contains, delete 3가지 메소드가 필요하다

1. insert