blob: 7c76727c57bd0168083dee7fe30853b629c46463 (
plain)
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
/*
package jnyqide;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Trie {
Node root;
/**
* Creates an WordMode object with the given dictionary.
*
* @param strs
* A list of strings containing the words in dictionary file which
* contains the list of valid words sorted by frequency
*/
/* public Trie()
{
root = new Node();
}
public void addWord(String word)
{
char[] letters = word.toCharArray();
Node n = root;
for(int i = 0; i < letters.length; i++)
{
if(n.get((int)letters[i]) == null)
{
Node x = n.addNode((int)letters[i]);
x.parent = n;
n = x;
}
else
n = n.get((int)letters[i]);
}
if(letters[letters.length-1] == ')')
word = "(" + word;
n.addWord(word);
while(n.parent != null)
{
n = n.parent;
n.addWord(word);
}
}
/* Since you are not allowed to use anything from java.util (except for the
* Iterator interface and AbstractList), you must create your own implementation
* of a list. (You may choose to extend AbstractList if you would like)
*
* If you would like to return an AbstractList,
* **Hint: What are the methods you need to implement in order to extend
* AbstractList? Also, in order for the AbstractList to function,
* what other methods must you override?
*/
// if full, must match all letters
/* public List getWordsFor(String s, Boolean full) {
char[] letters = s.toCharArray();
Node n = root;
for(int i = 0; i < letters.length; i++)
{
if(n.get((int)letters[i]) == null)
return (full ? null : n.unmodifiableList);
else
n = n.get((int)letters[i]);
}
return n.unmodifiableList;
}
public List getAllWordsFor(String s)
{
List r = new ArrayList<String>();
List l = getWordsFor("", false);
int i = 0;
while (i < l.size())
{
if (l.get(i).toString().contains(s)) {
r.add(l.get(i).toString());
}
i++;
}
return r;
}
private class Node {
Node parent;
Node nodes [] = new Node [128];
ArrayList <String> words = new ArrayList <String> ();
List unmodifiableList;
public Node()
{
parent = null;
unmodifiableList = Collections.unmodifiableList(new AbstractList() {
public int size() {
return words.size();
}
public String get(int i) {
return (String) words.get(i);
}
});
}
public Node get(int index)
{
return nodes[index];
}
public Node addNode(int i)
{
if(nodes[i] == null)
nodes[i] = new Node();
return nodes[i];
}
public void addWord(String str)
{
words.add(str);
// System.out.println("( " + str + " ) is added to Trie");
}
}
}
*/
|
