forked from onlybooks/java-algorithm-interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathP62_1.java
More file actions
77 lines (70 loc) · 3 KB
/
P62_1.java
File metadata and controls
77 lines (70 loc) · 3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package ch16;
public class P62_1 {
// 트라이의 노드
class TrieNode {
// 단어 완성 여부
boolean word;
// 트라이의 자식 노드들
TrieNode[] children;
public TrieNode() {
// 문제 제약 조건에 따라 소문자 알파벳으로 구성되므로 자식 노드는 알파벳의 개수인 최대 26개까지 가능
children = new TrieNode[26];
word = false;
}
}
class Trie {
TrieNode root;
// 클래스 생성시 루트로 빈 트라이 노드 생성
public Trie() {
root = new TrieNode();
}
// 단어 삽입
public void insert(String word) {
// 루트부터 시작
TrieNode cur = root;
// 단어의 문자를 차례대로 반복하며 자식 노드 구성
for (char c : word.toCharArray()) {
// 해당 문자의 자식 노드가 존재하지 않으면 신규 트라이 노드 생성
// 'a'가 인덱스 0, 'z'는 인덱스 25가 된다.
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
// 자식 노드를 현재 노드로 교체
cur = cur.children[c - 'a'];
}
// 단어가 완성된 후이므로 현재 노드는 단어 완성 여부에 true 설정
cur.word = true;
}
// 단어 존재 여부 판별
public boolean search(String word) {
// 루트부터 시작
TrieNode cur = root;
// 단어의 문자를 차례대로 반복하며 자식 노드 구성
for (char c : word.toCharArray()) {
// 자식 노드가 존재하지 않으면 false 리턴
if (cur.children[c - 'a'] == null)
return false;
// 자식 노드를 현재 노드로 교체
cur = cur.children[c - 'a'];
}
// 탐색이 종료된 후 단어 완성 여부를 리턴
// 완성된 단어가 아니라면 문자는 모두 매칭이 되어도 단어 완성 여부는 false일 수 있음
return cur.word == true;
}
// 문자열로 시작 단어 존재 여부 판별
public boolean startsWith(String prefix) {
// 루트부터 시작
TrieNode cur = root;
// 단어의 문자를 차례대로 반복하며 자식 노드 구성
for (char c : prefix.toCharArray()) {
// 자식 노드가 존재하지 않으면 false 리턴
if (cur.children[c - 'a'] == null)
return false;
// 자식 노드를 현재 노드로 교체
cur = cur.children[c - 'a'];
}
// 탐색이 종료되면 항상 true 리턴, 시작 여부만 판별하면 되므로 단어 완성 여부가 false여도 관계없음
return true;
}
}
}