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