Implement Trie and find longest prefix string list
29293 ワード
1 package leetcode;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 class TrieNode{
7 Boolean isWord;//true if path till this node represent a string.
8 Integer freq;//numbers of strings share the same prefix
9 Character nodeChar;//character for this node
10 ArrayList<TrieNode> childNodes;
11 public TrieNode(char c){
12 childNodes = new ArrayList<TrieNode>();
13 this.nodeChar = c;
14 this.freq = 1;
15 this.isWord = false;
16 }
17 public TrieNode(){
18 childNodes = new ArrayList<TrieNode>();
19 this.nodeChar = null;
20 this.freq = 0;
21 this.isWord = false;
22 }
23 }
24
25 class Prefix{
26 TrieNode root;
27 String prefix;
28 public Prefix(TrieNode root, String s){
29 this.root = root;
30 this.prefix = s;
31 }
32 }
33
34 public class Trie {
35 /*
36 Trie is an efficient information retrieval data structure.
37 Using trie, search complexities can be brought to optimal limit (key length).
38 If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N,
39 where M is maximum string length and N is number of keys in tree.
40 Using trie, we can search the key in O(M) time.
41 However the penalty is on trie storage requirements.
42 */
43 TrieNode root;
44 public Trie(){
45 root = new TrieNode();
46 }
47
48 public void insert(String s){
49 if(s == null || s.length() == 0) return;
50 TrieNode tmp = root;
51 tmp.freq ++;// prefix freq ++
52 for(int i = 0; i < s.length(); i ++){
53 Boolean hasNode = false;
54 for(int j = 0; j < tmp.childNodes.size(); j ++){
55 if(tmp.childNodes.get(j).nodeChar == s.charAt(i)){
56 tmp = tmp.childNodes.get(j);
57 tmp.freq ++;
58 hasNode = true;
59 break;
60 }
61 }
62 if(hasNode == false){
63 TrieNode newNode = new TrieNode(s.charAt(i));
64 tmp.childNodes.add(newNode);
65 tmp = newNode;
66 }
67 }
68 tmp.isWord = true;
69 }
70
71 public Boolean searchString(String s){
72 if(s == null || s.length() == 0) return false;
73 TrieNode tmp = root;
74 for(int i = 0; i < s.length(); i ++){
75 Boolean containsChar = false;
76 for(int j = 0; j < tmp.childNodes.size(); j ++){
77 if(tmp.childNodes.get(j).nodeChar == s.charAt(i)){
78 tmp = tmp.childNodes.get(j);
79 containsChar = true;
80 break;
81 }
82 }
83 if(containsChar == false){
84 return false;
85 }
86 }
87 return tmp.isWord == true;
88 }
89
90 /*
91 * During delete operation we delete the key in bottom up manner using recursion. The following are possible conditions when deleting key from trie,
92 * 1. Key may not be there in trie. Delete operation should not modify trie.
93 * 2. Key present as unique key (no part of key contains another key (prefix), nor the key itself is prefix of another key in trie). Delete all the nodes.
94 * 3. Key is prefix key of another long key in trie. Unmark the leaf node.
95 * 4. Key present in trie, having atleast one other key as prefix key. Delete nodes from end of key until first leaf node of longest prefix key.
96 */
97 public void delete(String s){
98 if(searchString(s) == false) return;
99 TrieNode tmp = root;
100 if(tmp.freq == 1){
101 tmp.childNodes.remove(0);
102 tmp.freq = 0;
103 return;
104 }
105 for(int i = 0; i < s.length(); i ++){
106 for(int j = 0; j < tmp.childNodes.size(); j ++){
107 if(tmp.childNodes.get(j).nodeChar == s.charAt(i)){
108 if(tmp.childNodes.get(j).freq == 1){
109 tmp.childNodes.remove(j);
110 tmp.freq --;
111 return;
112 }else{
113 tmp.childNodes.get(j).freq --;
114 tmp = tmp.childNodes.get(j);
115 }
116 break;
117 }
118 }
119 }
120 tmp.isWord = false;
121
122 }
123
124 //find a list of string in the dictionary, which contains the longest prefix with the target string
125 public List<String> findAllStringWithSameLongestPrefix(String s){
126 Prefix tmp = findLongestPrefix(s);
127 List<String> result = new ArrayList<String>();
128 if(tmp.root.equals(root)) return result;
129 findAllStringInSubTree(tmp.root, new StringBuilder(tmp.prefix), result);
130 return result;
131 }
132
133 private Prefix findLongestPrefix(String s){
134 TrieNode tmp = root;
135 StringBuilder sb = new StringBuilder();
136 for(int i = 0; i < s.length(); i ++){
137 Boolean containsChar = false;
138 for(int j = 0; j < tmp.childNodes.size(); j ++){
139 if(tmp.childNodes.get(j).nodeChar == s.charAt(i)){
140 sb.append(s.charAt(i));
141 tmp = tmp.childNodes.get(j);
142 containsChar = true;
143 break;
144 }
145 }
146 if(containsChar == false){
147 return new Prefix(tmp, sb.toString());
148 }
149 }
150 return new Prefix(tmp, s);
151 }
152
153 private void findAllStringInSubTree(TrieNode root, StringBuilder sb, List<String> result){
154 if(root.isWord == true){
155 result.add(sb.toString());
156 }
157 for(int i = 0; i < root.childNodes.size(); i ++){
158 TrieNode tmp = root.childNodes.get(i);
159 sb.append(tmp.nodeChar);
160 findAllStringInSubTree(tmp, new StringBuilder(sb), result);
161 sb.deleteCharAt(sb.length() - 1);
162 }
163 }
164
165 public static void main(String[] args){
166 Trie trie = new Trie();
167 System.out.println("insert string into Trie:");
168 System.out.println("a, aq, ab, abb, aa, bbd, bd, ba, abc");
169 trie.insert("a");
170 trie.insert("aq");
171 trie.insert("ab");
172 trie.insert("abb");
173 trie.insert("aa");
174 trie.insert("bbd");
175 trie.insert("bd");
176 trie.insert("ba");
177 trie.insert("abc");
178 System.out.println("search string in Trie:");
179 System.out.println("abb: " + trie.searchString("abb"));
180 System.out.println("bd: " + trie.searchString("bd"));
181 System.out.println("bda: " + trie.searchString("bda"));
182 System.out.println("strings start with a:");
183 List<String> list1 = trie.findAllStringWithSameLongestPrefix("a");
184 for(int i = 0; i < list1.size(); i ++){
185 System.out.println(list1.get(i));
186 }
187 System.out.println("strings start with b:");
188 List<String> list2 = trie.findAllStringWithSameLongestPrefix("b");
189 for(int i = 0; list2 != null && i < list2.size(); i ++){
190 System.out.println(list2.get(i));
191 }
192 System.out.println("strings start with ab:");
193 List<String> list3 = trie.findAllStringWithSameLongestPrefix("ab");
194 for(int i = 0; i < list3.size(); i ++){
195 System.out.println(list3.get(i));
196 }
197 System.out.println("strings start with abcdef:");
198 List<String> list4 = trie.findAllStringWithSameLongestPrefix("abcdef");
199 for(int i = 0; list4 != null && i < list4.size(); i ++){
200 System.out.println(list4.get(i));
201 }
202 System.out.println("delete string from trie:");
203 trie.delete("ab");
204 System.out.println(trie.searchString("ab"));
205 System.out.println(trie.searchString("abb"));
206 }
207 }Output:
insert string into Trie:
a, aq, ab, abb, aa, bbd, bd, ba, abc
search string in Trie:
abb: true
bd: true
bda: false
strings start with a:
a
aq
ab
abb
abc
aa
strings start with b:
bbd
bd
ba
strings start with ab:
ab
abb
abc
strings start with abcdef:
abc
delete string from trie:
false
true