LeetCode 208: 단어와 접두사를 구분하는 Trie 구현
경로가 있다고 단어인 것은 아닙니다
트라이(Trie)를 구현하는 문제입니다. 트라이는 문자열을 문자 단위로 저장합니다. 필요한 동작은 객체 생성, 단어 삽입, 단어 검색, 접두사 검색입니다.
처음에는 문자열을 문자로 나눠 노드에 하나씩 저장하는 구조를 생각했습니다. 그런데 경로가 존재하는 것과 단어가 저장되어 있는 것은 구분해야 했습니다.
apple만 넣은 상태라면 a → p → p 경로가 이미 있지만 search("app")은 false여야 합니다. 반면 startsWith("app")은 true입니다. 이 차이를 나타내기 위해 단어가 끝나는 노드에 isWord를 두었습니다.
입력이 영문 소문자로만 구성되므로 각 노드의 자식은 최대 26개입니다. 문자에서 'a'를 뺀 값을 자식 배열의 인덱스로 사용했습니다.
네 가지 동작을 나눴습니다
1. 생성자
모든 연산이 같은 시작점을 사용하도록 root를 멤버 변수로 두고 생성자에서 노드를 만듭니다. 루트는 특정 문자를 저장하지 않고 단어를 따라가기 위한 시작점으로 씁니다.
2. insert
루트부터 단어의 문자를 하나씩 확인합니다. 해당 문자의 자식이 있으면 이동하고 없으면 새 노드를 만든 뒤 이동합니다. 마지막 문자까지 처리하면 그 노드의 isWord를 true로 설정합니다.
3. search
루트부터 검색할 단어의 경로를 따라갑니다. 중간에 필요한 자식이 없으면 false를 반환하고 끝까지 도달하면 마지막 노드의 isWord를 반환합니다. 그래서 apple만 삽입했을 때 app을 완성된 단어로 판단하지 않습니다.
4. startsWith
경로를 확인하는 과정은 search와 같습니다. 다만 접두사만 확인하므로 끝에 도달했을 때 isWord를 보지 않고 true를 반환합니다.
코드
class TrieNode {
public boolean isWord;
public TrieNode[] children = new TrieNode[26];
}
public class Trie {
// (1)
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// (2)
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.isWord = true;
}
// (3)
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) return false;
node = node.children[c - 'a'];
}
return node.isWord;
}
// (4)
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if(node.children[c-'a']==null) return false;
node=node.children[c-'a'];
}
return true;
}
}