/***************************************************************************
* 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: isPrefix
* @param word
* @return boolean
*
* Description: Return true if the given word is a prefix.
* Return false otherwise.
*
* Technical Details: This method is similar to the isWord
* function. Except, the last line is different.
*
* 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] return false
* 4] set n to the node representing c.
* 5] At this point, n represent the last char in the word,
* so if n has children return true else return false.
****************************************************************/
public boolean isPrefix(String word) {
TrieNode n = root;
for (char c : word.toCharArray()) {
n = n.next[c];
if (null == n) {
return false;
}
}
return !n.nextIsEmpty;
}//isPrefix
}
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 isPrefix method, of class Trie.
*/
@Test
public void testIsPrefix() {
System.out.println("isPrefix");
String dictionary[] = {"fame", "is", "the", "spur", "that", "the",
"clear", "spirit", "doth", "raise", "that", "last", "infirmity", "of",
"noble", "mind", "to", "scorn", "delights", "and", "live", "laborious",
"days"};
Trie trie = new Trie();
for (String w : dictionary) {
trie.addWord(w);
}
assertTrue(trie.isPrefix("th"));//the, that
assertFalse(trie.isPrefix("fame"));
}
}