[LeetCode/Top Interview 150] [Trie] 208. Implement Trie (Prefix Tree)
LeetCode Top Interview 150
문제 링크: https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)
난이도: medium
문제:
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.Example 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 TrueConstraints:
1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.
전략:
문자열을 입력박아 저장하고 검색하는 트라이 자료구조를 구현하는 문제.
내부에 Node 클래스를 구현하여 char 자료형의 형태로 알파벳을 저장하고, HashMap으로 다음 노드를 참조하는 방식으로 구현.
코드 구현:
class Trie {
Node head;
Node dummy = new Node(' '); // Dummy Head용 빈 노드.(들어올 자료들은 모두 영문 소문자만 들어온다.)
class Node { // Node 클래스
char val; // 값(생략 가능)
HashMap<Character, Node> children;
boolean end = false;
Node(char val) {
this.val = val;
this.children = new HashMap<Character, Node>();
this.end = false;
}
}
public Trie() {
head = dummy;
}
public void insert(String word) {
HashMap<Character, Node> next = head.children; // 더미 헤드의 칠드런(다음 노드들)
for (int i=0;i<word.length();i++) { // 문자열을 순회하며 알파벳 체크
char now = word.charAt(i); // 지금 체크하는 알파벳
if (next.containsKey(now)) { // 다음 노드들중에 이 알파벳이 포함되어 있는지
// 이미 존재하는 노드
if (i==word.length()-1) { // 현재 문자열의 마지막 문자라면
next.get(now).end = true; // end를 true로 변경
}
next = next.get(now).children; // 다음 노드들 현재 노드의 children으로 변경
} else {
// 아직 이 문자의 노드가 없다면
Node input = new Node(now); // 추가할 노드
if (i==word.length()-1) { input.end = true; } // 마지막 문자라면 end = true;
next.put(now, input); // 추가
next = next.get(now).children; // 다음 노드들 현재 추가한 노드의 children으로 변경
}
}
}
public boolean search(String word) {
HashMap<Character, Node> next = head.children; // 더미 헤드의 칠드런(다음 노드들)
for (int i=0;i<word.length();i++) {
char now = word.charAt(i);
if (next.containsKey(now)) { // 키가 있다면
if (i == word.length()-1) { // 마지막 문자열이라면
if (next.get(now).end) { // end가 true라면(정확히 이 문자열이 입력된 적이 있다면)
return true;
} else {
return false;
}
}
next = next.get(now).children; // 다음 노드들 현재 추가한 노드의 children으로 변경
} else {
return false; // 없다면 바로 false 리턴하여 탈출
}
}
return true; // 끝까지 체크 후 false 아니라면 true
}
public boolean startsWith(String prefix) {
HashMap<Character, Node> next = head.children; // 더미 헤드의 칠드런(다음 노드들)
for (int i=0;i<prefix.length();i++) {
char now = prefix.charAt(i);
if (next.containsKey(now)) { // 키가 있다면
next = next.get(now).children; // 다음 노드 탐색
} else {
return false; // 없다면 바로 false 리턴하여 탈출
}
}
return true; // 끝까지 체크 후 false 아니라면 true
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
Time: 45 ms (24.47%), Space: 55.5 MB (11.81%) - LeetHub개선 방안:
Node 클래스 내부의 사용되지 않는 변수 val 제거.
class Trie {
Node head;
Node dummy = new Node(); // Dummy Head용 빈 노드
class Node { // Node 클래스
HashMap<Character, Node> children;
boolean end = false;
Node() {
this.children = new HashMap<Character, Node>();
this.end = false;
}
}
public Trie() {
head = dummy;
}
public void insert(String word) {
HashMap<Character, Node> next = head.children; // 더미 헤드의 칠드런(다음 노드들)
for (int i=0;i<word.length();i++) { // 문자열을 순회하며 알파벳 체크
char now = word.charAt(i); // 지금 체크하는 알파벳
if (next.containsKey(now)) { // 다음 노드들중에 이 알파벳이 포함되어 있는지
// 이미 존재하는 노드
if (i==word.length()-1) { // 현재 문자열의 마지막 문자라면
next.get(now).end = true; // end를 true로 변경
}
next = next.get(now).children; // 다음 노드들 현재 노드의 children으로 변경
} else {
// 아직 이 문자의 노드가 없다면
Node input = new Node(); // 추가할 노드
if (i==word.length()-1) { input.end = true; } // 마지막 문자라면 end = true;
next.put(now, input); // 추가
next = next.get(now).children; // 다음 노드들 현재 추가한 노드의 children으로 변경
}
}
}
public boolean search(String word) {
HashMap<Character, Node> next = head.children; // 더미 헤드의 칠드런(다음 노드들)
for (int i=0;i<word.length();i++) {
char now = word.charAt(i);
if (next.containsKey(now)) { // 키가 있다면
if (i == word.length()-1) { // 마지막 문자열이라면
if (next.get(now).end) { // end가 true라면(정확히 이 문자열이 입력된 적이 있다면)
return true;
} else {
return false;
}
}
next = next.get(now).children; // 다음 노드들 현재 추가한 노드의 children으로 변경
} else {
return false; // 없다면 바로 false 리턴하여 탈출
}
}
return true; // 끝까지 체크 후 false 아니라면 true
}
public boolean startsWith(String prefix) {
HashMap<Character, Node> next = head.children; // 더미 헤드의 칠드런(다음 노드들)
for (int i=0;i<prefix.length();i++) {
char now = prefix.charAt(i);
if (next.containsKey(now)) { // 키가 있다면
next = next.get(now).children; // 다음 노드 탐색
} else {
return false; // 없다면 바로 false 리턴하여 탈출
}
}
return true; // 끝까지 체크 후 false 아니라면 true
}
}
Time: 45 ms (24.47%), Space: 55.3 MB (21.62%) - LeetHubSolutions 탭의 타인 코드:
class TrieNode {
boolean isEnd;
TrieNode[] children;
public TrieNode() {
isEnd = true;
children = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode current = root;
for(int i=0, L=word.length(); i<L; i++) {
int id = word.charAt(i) - 'a';
if(current.children[id]==null) {
current.children[id] = new TrieNode();
current.children[id].isEnd = false;
}
current = current.children[id];
}
current.isEnd = true;
}
public boolean search(String word) {
return search(word, 1);
}
public boolean startsWith(String prefix) {
return search(prefix, 2);
}
private boolean search(String str, int type) {
TrieNode current = root;
int i=-1, L=str.length();
while(++i<L) {
int id = str.charAt(i) - 'a';
if((current=current.children[id]) == null) return false;
}
return type==1 ? current.isEnd : true;
}
}
Time: 34 ms (83.07%), Space: 54.3 MB (90.77%) - LeetHub회고:
문제 내부의 성능측면에서는 확실히 영문 소문자라는 제약이 걸려 있으므로 배열로 저장하여 푸는 방식도 괜찮겠지만, 이러한 구현 문제의 경우 실제로 사용하는 경우를 생각해 보다 범용적인 사용을 전제로 구현하는 것도 좋을 것 같다.
생각한 만큼의 성능 차도 나오지 않은 것 같다.
