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  

Comments

RSS Icon Subscribe to comments
Posted By: JhonConstantine01 on January 3, 2019

Windows 10 user wants to access the program faster so just from here learn how to open command prompt in windows 10 operating system easily.

You need to login to post a comment.