Is Prefix
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/***************************************************************************
 * 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
}