(Leetcode) 208 - Implement Trie (Prefix Tree)
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/implement-trie-prefix-tree/
내가 작성한 풀이
class Trie {
Node root = new Node();
public Trie() {
}
public void insert(String word) {
Node currentNode = root;
for(char c : word.toCharArray()) {
if(currentNode.nodes[c - 97] == null) {
currentNode.nodes[c - 97] = new Node();
}
currentNode = currentNode.nodes[c - 97];
}
currentNode.val = word;
}
public boolean search(String word) {
Node currentNode = root;
for(char c : word.toCharArray()) {
if(currentNode.nodes[c - 97] == null) {
return false;
}
currentNode = currentNode.nodes[c - 97];
}
return currentNode.val != null && currentNode.val.equals(word);
}
public boolean startsWith(String prefix) {
Node currentNode = root;
for(char c : prefix.toCharArray()) {
if(currentNode.nodes[c - 97] == null) {
return false;
}
currentNode = currentNode.nodes[c - 97];
}
return true;
}
}
class Node {
String val;
Node[] nodes = new Node[26];
}
TC, SC
insert, search, startsWith 메소드의 경우 입력된 문자열의 길이를 n 이라 하였을 때 시간 복잡도는 O(n)이다. 공간 복잡도는 insert된 문자열의 갯수 를 N 이라 하고 insert된 문자열의 길이의 평균 를 L이라고 하였을 때 O(N * L * 26)이다. 26은 계수이기 때문에 생략할 수 있다.