#
Add Word

/*************************************************************************** * Author: Isai Damier * Title: Trie.java * Project: geekviewpoint * Package: datastructure * * Description: * A trie is a tree data-structure that stores words by compressing common * prefixes. To illustrate, following is a word list and its resulting trie. * * WORDS: rat, rats, rattle, rate, rates, rating, can, cane, * canny, cant, cans, cat, cats, cattle, cattles. * * TRIE: * ___________|____________ * | | * r c * a ________a___________ * t~ | | * ____|_____ n~ t~ * | | | | _____|_____ _______|______ * s~ t e~ i | | | | | t * l s~ n e~ n t~ s~ s~ l * e~ g~ y~ e~ * s~ * * Each ~ in the figure indicates where a prefix is a word. * * Generally, a trie has all the benefits of a hash table without * any of the disadvantages. * * -------------------------------------------------------------- * | HASH TABLE | TRIE | explanations * -------------------------------------------------------------- * Memory | O(n) | < O(n) | trie uses prefix compression. * | | | Hence it does not store each * | | | word explicitly * ---------------------------------------------------------------- * Search | O(1) | O(1) | trie is technically faster. * | | pseudo- | Given a word, computing a * | | constant | hash takes at least as long * | | | as traversing a trie. Plus, * | | | trie has no collision. * ---------------------------------------------------------------- * * Tries are particularly superior to hash tables when it comes to solving * problems such as word puzzles like boggle. In such puzzles the objective * is to find how many words in a given list are valid. So if for example * at a particular instance in boggle you have a list of one billion words * all starting with zh-, whereas the dictionary has no words starting with * zh-; then: if the dictionary is a hash table, you must compute the entire * hashcode for each word and do one billion look-ups; if on the other hand * the dictionary is a trie, you only do the equivalent of partially * computing one hashcode! That's a saving of over one billion fold! * * This implementations of trie uses an array to store the children * nodes, where the numerical value of each char serves as index. **************************************************************************/ package algorithms.trie; import java.util.ArrayList; import java.util.List; import java.util.Stack; public class Trie { //the root only serves to anchor the trie. private TrieNode root; public Trie() { root = new TrieNode('\0'); }//constructor /****************************************************************** * Function: addWord * @param word * @return boolean * * Description: Insert the given word into the trie. If the word * already exists, return false; else return true. * * Technical Details: A word is added to a trie one letter at a time. * * 0] Start with the root of the trie as the current node n. * 1] for each character c * 2] if c is not among the children of n * 3] add c to the children of n * 4] set n to the node representing c. * 5] At this point, n represent the last char in the word, * so if n is marked return false since word already exists * else mark n as word and return true. ****************************************************************/ public boolean addWord(String word) { TrieNode n = root, tmp; for (char c : word.toCharArray()) { tmp = n.next[c]; if (tmp == null) { tmp = new TrieNode(c); n.setChild(c, tmp); } n = tmp; } if (n.word) { return !n.word; } n.word = true; return n.word; }//addWord }

package algorithms.graph; import java.util.Arrays; import java.util.Collections; import java.util.List; import org.junit.Test; import static org.junit.Assert.*; /*** * The dictionary is assembled from the works of poet * Percy Bysshe Shelley (1792-1822) ***/ public class TrieTest { /** * Test of addWord method, of class Trie. */ @Test public void testAddWord() { System.out.println("addWord"); String dictionary[] = {"alas", "what", "boots", "it", "with", "incessant", "care", "to", "tend", "the", "homely", "slighted", "shepherd's", "trade"}; Trie trie = new Trie(); for (String word : dictionary) { if (!trie.addWord(word)) { fail(word + " already in trie"); } } if (trie.addWord(dictionary[0])) { fail("Trie not working properly"); } } }