Posted By

edwarddr on 07/01/12


Tagged

problem quiz linkedlist trie


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

edwarddr


Trie with LinkedList


 / Published in: Java
 

A short practice to write a trie with LinkedList for all the valid words

  1. /*
  2.  * Author: Ruo Ding
  3.  * Date: June 26, 2012
  4.  */
  5. import java.io.File;
  6. import java.util.ArrayList;
  7. import java.util.Hashtable;
  8. import java.util.Scanner;
  9.  
  10.  
  11. public class SimpleTrie {
  12.  
  13. /**
  14. * @param args
  15. */
  16. private SimpleTrieNode root;
  17. private SimpleTrieNode head;
  18. public SimpleTrie()
  19. {
  20. root = new SimpleTrieNode();
  21. head = null;
  22. }
  23.  
  24. public void initTrie(String aWord)
  25. {
  26. if (head!=null)
  27. return;
  28.  
  29. SimpleTrieNode scanningNode = root;
  30. for (int i = 0; i < aWord.length(); i++)
  31. {
  32. char letter = aWord.charAt(i);
  33. int iChar = Character.getNumericValue(letter) - 10;
  34. String subWord = aWord.substring(0, i+1);
  35. scanningNode.subNodes[iChar] = new SimpleTrieNode(subWord);
  36. scanningNode = scanningNode.subNodes[iChar];
  37. }
  38. scanningNode.isWord = true;
  39. head = scanningNode;
  40. }
  41.  
  42. public void insert(String word)
  43. {
  44. SimpleTrieNode scanningNode = root;
  45. String aWord = word.toLowerCase();
  46.  
  47. if (head == null)
  48. {
  49. initTrie(aWord);
  50. return;
  51. }
  52.  
  53. SimpleTrieNode nextWord = null;
  54. SimpleTrieNode prevWord = null;
  55. for (int i = 0; i < aWord.length(); i++)
  56. {
  57. char letter = aWord.charAt(i);
  58. int iChar = Character.getNumericValue(letter) - 10;
  59. if (scanningNode.subNodes[iChar] != null)
  60. {
  61. scanningNode = scanningNode.subNodes[iChar];
  62.  
  63. if (scanningNode.values.length == aWord.length() &&
  64. scanningNode.toString().equals(aWord) &&
  65. !scanningNode.isWord)
  66. {
  67. // if the word occur as a prefix in our list,
  68. // than find the fist word with this prefix, insert this in the front
  69. nextWord = findNextWord(scanningNode, 0);
  70. scanningNode.isWord = true;
  71. if (nextWord.prev != null)
  72. {
  73. prevWord = nextWord.prev;
  74. prevWord.next = scanningNode;
  75. scanningNode.prev = prevWord;
  76. }
  77.  
  78. scanningNode.next = nextWord;
  79. nextWord.prev = scanningNode;
  80. return;
  81. }
  82. }else
  83. {
  84. if (prevWord == null && nextWord == null)
  85. {
  86. nextWord = findNextWord(scanningNode, iChar+1);
  87. prevWord = findPrevWord(scanningNode, iChar-1);
  88. }
  89. String subWord = aWord.substring(0, i+1);
  90. scanningNode.subNodes[iChar] = new SimpleTrieNode(subWord);
  91. scanningNode = scanningNode.subNodes[iChar];
  92. }
  93. }
  94. scanningNode.isWord = true;
  95.  
  96. if (prevWord != null)
  97. {
  98. prevWord.next = scanningNode;
  99. scanningNode.prev = prevWord;
  100. }
  101. if (nextWord != null)
  102. {
  103. nextWord.prev = scanningNode;
  104. scanningNode.next = nextWord;
  105. }
  106. }
  107.  
  108. public SimpleTrieNode find(String word)
  109. {
  110. if (head == null)
  111. {
  112. return null;
  113. }
  114.  
  115.  
  116. SimpleTrieNode scanningNode = root;
  117. String aWord = word.toLowerCase();
  118. for (int i = 0; i < aWord.length(); i++)
  119. {
  120. char letter = aWord.charAt(i);
  121. int iChar = Character.getNumericValue(letter) - 10;
  122. if (scanningNode.subNodes[iChar] != null)
  123. {
  124. scanningNode = scanningNode.subNodes[iChar];
  125. if (scanningNode.values.length == aWord.length())
  126. {
  127. if (scanningNode.isWord)
  128. {
  129. return scanningNode;
  130. }else
  131. {
  132. return null;
  133. }
  134. }
  135. }else
  136. {
  137. return null;
  138. }
  139. }
  140.  
  141. return null;
  142. }
  143.  
  144. public SimpleTrieNode remove(String word)
  145. {
  146. SimpleTrieNode toRemove = find(word);
  147. if(toRemove.prev!=null)
  148. {
  149. toRemove.prev.next = toRemove.next;
  150. }
  151. if(toRemove.next!=null)
  152. {
  153. toRemove.next.prev = toRemove.prev;
  154. }
  155. return toRemove;
  156. }
  157.  
  158.  
  159. public SimpleTrieNode getHead() {
  160. return head;
  161. }
  162.  
  163. // give the parent node and the index starts to scan in parent node
  164. public SimpleTrieNode findNextWord(SimpleTrieNode node, int cIndex)
  165. {
  166. if (node == null)
  167. return null;
  168.  
  169. String subWord = node.toString();
  170.  
  171. for (int i = cIndex; i<node.subNodes.length; i++)
  172. {
  173. if (node.subNodes[i] != null)
  174. {
  175. if (node.subNodes[i].isWord)
  176. {
  177. return node.subNodes[i];
  178. }else
  179. {
  180. return findNextWord(node.subNodes[i], 0);
  181. }
  182. }
  183. }
  184.  
  185. // none found in the same or below level, proceed to the next in its parent level
  186. SimpleTrieNode theParent = null;
  187. for (int i = 0; i < subWord.length()-1; i++)
  188. {
  189. if (theParent == null)
  190. {
  191. theParent = root;
  192. }
  193. char letter = subWord.charAt(i);
  194. int iChar = Character.getNumericValue(letter) - 10;
  195. if (theParent.subNodes[iChar]!=null)
  196. {
  197. theParent = theParent.subNodes[iChar];
  198. }else
  199. {
  200. return null;
  201. }
  202. }
  203.  
  204. int nextIndex = -1;
  205. if (subWord.length()>=1)
  206. {
  207. char nextChar = subWord.charAt(subWord.length()-1);
  208. nextIndex = Character.getNumericValue(nextChar) - 10;
  209. }
  210. return findNextWord(theParent, nextIndex+1);
  211.  
  212. }
  213.  
  214. // give the parent node and the index starts to scan in parent node
  215. public SimpleTrieNode findPrevWord(SimpleTrieNode node, int cIndex)
  216. {
  217. if (node == null)
  218. return null;
  219.  
  220. String subWord = node.toString();
  221.  
  222. for (int i = cIndex; i >= 0; i--)
  223. {
  224. if (node.subNodes[i] != null)
  225. {
  226. SimpleTrieNode rSubNode = findPrevWord(node.subNodes[i], 25);
  227. if (rSubNode != null)
  228. {
  229. return rSubNode;
  230. }else if (node.subNodes[i].isWord)
  231. {
  232. return node.subNodes[i];
  233. }
  234. }
  235. }
  236.  
  237. //if none exist before the index in the node child, check if node is a word
  238. if (node.isWord)
  239. {
  240. return node;
  241. }
  242.  
  243. // none found in the same or below level, proceed to the prev in its parent level
  244. SimpleTrieNode theParent = null;
  245. int iChar = -1;
  246. int i;
  247. for ( i = 0; i < subWord.length()-1; i++)
  248. {
  249. if (theParent == null)
  250. {
  251. theParent = root;
  252. }
  253. char letter = subWord.charAt(i);
  254. iChar = Character.getNumericValue(letter) - 10;
  255. if (theParent.subNodes[iChar]!=null)
  256. {
  257. theParent = theParent.subNodes[iChar];
  258. }else
  259. {
  260. return null;
  261. }
  262. }
  263. int nextIndex = -1;
  264. if (subWord.length()>=1)
  265. {
  266. char nextChar = subWord.charAt(subWord.length()-1);
  267. nextIndex = Character.getNumericValue(nextChar) - 10;
  268. }
  269. return findPrevWord(theParent, nextIndex-1);
  270.  
  271. }
  272.  
  273.  
  274. // main just test some basic functions for this SimpleTrie
  275. public static void main(String[] args) {
  276.  
  277. SimpleTrie ourTrie = new SimpleTrie();
  278. File dbFile = new File("dictionary.txt");
  279. int wordsCount = 0;
  280. int nodesCount = 0;
  281. ArrayList<String> allWords = new ArrayList<String>();
  282. Hashtable<String, Integer> table = new Hashtable<String, Integer>();
  283. int duplicateCounts = 0;
  284. try{
  285.  
  286. if (dbFile.exists())
  287. {
  288. Scanner preProcessor = new Scanner(dbFile);
  289. while (preProcessor.hasNextLine())
  290. {
  291.  
  292. String theWord = preProcessor.nextLine();
  293. if (theWord.equals("abalone"))
  294. {
  295. System.out.println("Hit abalone");
  296. }
  297. ourTrie.insert(theWord);
  298. allWords.add(theWord);
  299. wordsCount++;
  300. if (table.get(theWord)!=null)
  301. {
  302. duplicateCounts++;
  303. }
  304. table.put(theWord, new Integer(1));
  305. }
  306. preProcessor.close();
  307. }
  308. SimpleTrieNode aR = ourTrie.remove("zimbalon");
  309. System.out.println(aR.toString());
  310. SimpleTrieNode printNode = ourTrie.getHead();
  311. while(printNode!=null)
  312. {
  313. //System.out.println(printNode.toString());
  314. printNode = printNode.next;
  315. nodesCount++;
  316. }
  317.  
  318. for (int i = 0; i< allWords.size(); i++)
  319. {
  320. String aWord = allWords.get(i);
  321. if (ourTrie.find(aWord) == null)
  322. {
  323. System.out.println("Word: \'" + aWord + "\' not found!");
  324. }
  325. }
  326.  
  327.  
  328. }catch(Exception e)
  329. {
  330. System.out.println("Faild with Error: " + e.getMessage() + ", at line: " + wordsCount + ", at node " + nodesCount);
  331. }
  332.  
  333.  
  334.  
  335. System.out.println("TotalWord from dic is: " + wordsCount + ", and total nodes is: " + nodesCount + ", dupcount: " + duplicateCounts);
  336.  
  337. }
  338.  
  339. }
  340.  
  341.  
  342.  
  343.  
  344. public class SimpleTrieNode {
  345.  
  346. /**
  347. * @param args
  348. */
  349. public SimpleTrieNode prev;
  350. public SimpleTrieNode next;
  351. public SimpleTrieNode[] subNodes;
  352. public char[] values;
  353. public char sValue;
  354. public boolean isWord; // true indicate the node contains a word in our dictionary
  355.  
  356. public SimpleTrieNode()
  357. {
  358. prev = null;
  359. next = null;
  360. subNodes = new SimpleTrieNode[26];
  361. }
  362.  
  363. public SimpleTrieNode(String word)
  364. {
  365. prev = null;
  366. next = null;
  367. subNodes = new SimpleTrieNode[26];
  368. values = word.toCharArray();
  369. if (values.length >= 1)
  370. {
  371. sValue = values[values.length-1];
  372. }
  373. }
  374.  
  375.  
  376. public String toString()
  377. {
  378. if (values == null)
  379. return "";
  380.  
  381. return new String(values);
  382. }
  383. }

Report this snippet  

You need to login to post a comment.