/
Main.java
82 lines (67 loc) · 2.01 KB
/
Main.java
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
import java.util.*;
class Solution {
public int[] solution(String msg) {
Trie rootTrie = this.initTrie();
int[] printedIdx = this.editDictionary(msg, rootTrie);
return printedIdx;
}
private Trie initTrie(){
Trie rootTrie = new Trie('0', 0);
int idx = 1;
for(int i = (int)'A'; i <= (int)'Z'; i++){
rootTrie.setNext((char)i, idx);
idx++;
}
return rootTrie;
}
private int[] editDictionary(String msg, Trie rootTrie){
List<Integer> result = new ArrayList<Integer>();
int idx = 27;
for(int i = 0; i < msg.length(); i++){
char word = msg.charAt(i);
Trie trieChain = rootTrie;
while(trieChain.hasNext(word)){
trieChain = trieChain.next(word);
i++;
if(i == msg.length()) break;
word = msg.charAt(i);
}
trieChain.setNext(word, idx);
result.add(trieChain.getIdx());
idx++;
i--;
}
return this.convertToArray(result);
}
private int[] convertToArray(List<Integer> list){
int[] resultArray = new int[list.size()];
for(int i = 0; i < list.size(); i++) resultArray[i] = list.get(i);
return resultArray;
}
}
class Trie{
private char word;
private int idx;
private Trie[] nextTries;
public Trie(char word, int idx){
this.word = word;
this.idx = idx;
this.nextTries = new Trie[26];
}
public char getWord(){
return this.word;
}
public void setNext(char c, int idx){
if(this.hasNext(c)) return;
this.nextTries[(int)c-(int)'A'] = new Trie(c, idx);
}
public Trie next(char c){
return this.nextTries[(int)c-(int)'A'];
}
public boolean hasNext(char c){
return this.nextTries[(int)c-(int)'A'] != null;
}
public int getIdx(){
return this.idx;
}
}