[LeetCode Top Interview 150]
[문제 링크]
[문제 설명]
- trie ("try"로 발음) or prefix tree 는 문자열 데이터셋에서 키를 효율적으로 저장하고 검색하는데 사용되는 트리 데이터 구조
- Trie 클래스 구현
- Trie() : 개체를 초기화
- void insert(String word) : 문자열 word를 Trie에 삽입
- booelan search(String word) : 문자열이 word트라이에 있는지(즉, 이전에 삽입되었는지) 확인하여 있다면 true 반환, 그렇지 않다면 false 반환
- bollean startsWith(String prefix) : 이전에 삽입된 문자열에 prefix 접두사가 있으면 true 반환, 그렇지 않으면 false 반환
[예시1]
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"][], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
[제약]
- 1 <= word.length, prefix.length <= 2000
- word와 prefix는 영문 소문자로만 구성
- 최대 호출 횟수는 3 * 104 (insert, search and startsWith)
[코드를 작성하기 전에]
일단 수업 내용을 이해하고, 복습하는 차원에서 천천히 코드를 작성해보았다. Trie를 사용하는 가장 중요한 이유는 문자열 검색에 최적화된 자료구조이기 때문이다. 완전한 단어 검색이라면 해시 테이블을 사용하는 것이 더 효율적이라고 한다. (시간 복잡도가 O(1))
그러나, 트라이 같은 경우 사전 순 정렬이 가능하고, 시간 복잡도는 해시 테이블보다는 조금 느리다.
[시간 복잡도]
접두어 탐색 부분 : 상수 시간 O(p) / 재귀적 탐색 부분 : O(n)
[공간 복잡도]
- 재귀의 깊이는 트라이의 최대 높이나 깊이에 비례
- 트라이의 깊이는 문자열의 최대 길이로 제한되며, 이 최대 깊이를 d라고 할 때 재귀 호출로 인해 공간 복잡도는 O(d)
[작성 코드]
1) Node 클래스
class Node {
public Map<Character, Node> children;
public boolean isEndOfWord;
public Node() {
this.children = new HashMap<>();
this.isEndOfWord = false;
}
}
- 문자를 자식 노드로 가지는 children 객체
- 현재 노드가 단어의 끝인지 나타내는 boolean 타입 isEndOfWord 변수
2) Trie 클래스
private Node root;
public Trie() {
this.root = new Node();
}- Tire 객체는 새로운 Root 노드 root를 생성
- 이 Root 노드가 모든 문자열의 시작점을 의미한다.
3) insert 메서드
public void insert(String word) {
insert(this.root, word);
}- Trie에 문자열 word를 삽입하는 메서드 insert
- root 노드부터 시작하여 문자열의 각 문자(Char)를 순회하면서 Trie를 구성한다.
4) insert 메서드 (재귀)
public void insert(Node node, String word) {
if (word.length() == 0) {
node.isEndOfWord = true;
return;
}
final char c = word.charAt(0);
Node child = node.children.get(c);
if (child == null) {
child = new Node();
node.children.put(c, child);
}
insert(child, word.substring(1));
}- 재귀 탐색
- 해당 문자에 대한 자식 노드가 없는 경우, 새로운 노드를 생성하고 children 객체에 추가한다.
- 문자열 word의 길이가 0인 경우 해당 노드를 단어의 끝(isEndOfWord)을 true로 표시
5) search 메서드
public boolean search(String word) {
return search(this.root, word);
}- Trie에 문자열 word를 검색하는 메서드 search
- root 노드부터 시작하여 문자열의 각 문자(Char)를 순회하면서 Trie를 검색
6) search 메서드 (재귀)
private boolean search(final Node node, final String word) {
if (word.length() == 0) {
return node.isEndOfWord;
}
char c = word.charAt(0);
Node child = node.children.get(c);
if (child == null) {
return false;
}
return search(child, word.substring(1));
}- 해당 문자에 대한 자식 노드가 없는 경우, Trie에 해당 문자열이 존재하지 않는 것이므로 false 반환
- 그렇지 않으면, 마지막 노드의 isEndOfWord 값을 반환하여 해당 문자열이 Trie에 있는지 여부 확인
7) startsWith 메서드
public boolean startsWith(String prefix) {
return startsWith(this.root, prefix);
}- Trie에 접두사 prefix가 있는지 확인하는 메서드 startsWith
- root 노드부터 시작하여 접두사의 각 문자(Char)를 순회하면서 Trie를 검색
8) startsWith 메서드 (재귀)
public boolean startsWith(String prefix) {
Node currentNode = this.root;
for (char c: prefix.toCharArray()) {
Node child = currentNode.children.get(c);
if (child == null) return false;
currentNode = child;
}
return true;
}- 접두사의 모든 문자가 Trie에 존재한다면 true, 없다면 false 반환
9) 전체 코드
class Trie {
class Node {
public Map<Character, Node> children;
public boolean isEndOfWord;
public Node() {
this.children = new HashMap<>();
this.isEndOfWord = false;
}
}
private Node root;
public Trie() {
this.root = new Node();
}
public void insert(String word) {
insert(this.root, word);
}
public void insert(Node node, String word) {
if (word.length() == 0) {
node.isEndOfWord = true;
return;
}
final char c = word.charAt(0);
Node child = node.children.get(c);
if (child == null) {
child = new Node();
node.children.put(c, child);
}
insert(child, word.substring(1));
}
public boolean search(String word) {
return search(this.root, word);
}
private boolean search(final Node node, final String word) {
if (word.length() == 0) {
return node.isEndOfWord;
}
char c = word.charAt(0);
Node child = node.children.get(c);
if (child == null) {
return false;
}
return search(child, word.substring(1));
}
public boolean startsWith(String prefix) {
return startsWith(this.root, prefix);
}
private boolean startsWith(final Node node, final String prefix) {
Node currentNode = this.root;
for (char c: prefix.toCharArray()) {
Node child = currentNode.children.get(c);
if (child == null) return false;
currentNode = child;
}
return true;
}
}
[회고]
Trie 이론이나 동작 원리 부분은 굉장히 흥미롭고 재밌었는데, 실제로 구현하려니까 어려웠다.. 자료구조, 알고리즘.. 갈 길이 먼 것 같다…
Ad Astra