기본코드
|
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
|
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main{
static Scanner sc = new Scanner(System.in);
static class Trie{
TrieNode root = new TrieNode();
void insert(String key){
root.insert(key);
}
boolean find(String key){
return root.find(key);
}
}
static class TrieNode{
TrieNode[] next = new TrieNode[26];
boolean leaf;
void insert(String str){
TrieNode cur = this;
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(i == str.length() - 1){
cur.leaf = true;
break;
}
if(cur.next[c - 'a'] == null)
cur.next[c - 'a'] = new TrieNode();
cur = cur.next[c - 'a'];
}
}
boolean find(String str){
TrieNode cur = this;
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(cur.next[c - 'a'] == null){
if(i == str.length() - 1)
break;
return false;
}
cur = cur.next[c - 'a'];
}
return true;
}
}
public static void main(String []args){
Trie trie = new Trie();
trie.insert("apple");
trie.insert("orange");
}
}
|
특정 문자열 개수 코드(응용)
|
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main{
static Scanner sc = new Scanner(System.in);
static class Trie{
TrieNode root = new TrieNode();
void insert(String key){
root.insert(key);
}
boolean find(String key){
return root.find(key);
}
int getCount(String key){
return root.getCount(key);
}
}
static class TrieNode{
TrieNode[] next = new TrieNode[26];
int cnt = 0;
boolean leaf;
void insert(String str){
TrieNode cur = this;
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(i == str.length() - 1){
cur.leaf = true;
break;
}
if(cur.next[c - 'a'] == null)
cur.next[c - 'a'] = new TrieNode();
cur = cur.next[c - 'a'];
cur.cnt += 1;
}
}
boolean find(String str){
TrieNode cur = this;
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(cur.next[c - 'a'] == null){
if(i == str.length() - 1)
break;
return false;
}
cur = cur.next[c - 'a'];
}
return true;
}
int getCount(String str){
TrieNode cur = this;
for(int i = 0; i < str.length(); i++){
char c = str.charAt(i);
if(cur.next[c - 'a'] == null)
break;
cur = cur.next[c - 'a'];
if(i == str.length() - 1)
return cur.cnt;
}
return 0;
}
}
public static void main(String []args){
Trie trie = new Trie();
trie.insert("apple");
trie.insert("orange");
trie.insert("apart");
trie.insert("abort");
trie.insert("apx");
System.out.println(trie.getCount("a"));
}
}
|
'알고리즘 > JAVA' 카테고리의 다른 글
| 2차원 배열 회전시키기(Rotate, Rotate Image, Java) (0) | 2021.04.24 |
|---|---|
| [JAVA] 소수점 자릿수 출력하기(백준 3053, 택시 기하학) (0) | 2020.08.15 |
| 자바 공백포함 문자열 읽고 단어 단위로 자르기 (0) | 2020.08.02 |