package advanced.datastructure.trie.lc208_implementtrie;

/**
 */
public class Trie {

    private TrieNode root;

    public Trie() { root = new TrieNode(); }

    public void insert(String word) {
        TrieNode node = search(word, true);
        node.isWord = true; /* node cannot be null */
    }

    public boolean search(String word) {
        TrieNode node = search(word, false);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = search(prefix, false);
        return node != null; // no need to do dfs search here
    }

    private TrieNode search(String word, boolean isCreate) {
        TrieNode node = root; /* invariant: node correspond to word[i-1] => entire word when terminate */
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                if (isCreate) node.children[idx] = new TrieNode();
                else return null;
            }
            node = node.children[idx];
        }
        return node;
    }

    private boolean dfs(TrieNode node) {
        if (node == null) return false;
        if (node.isWord) return true;
        for (TrieNode n : node.children)
            if (dfs(n)) return true;
        return false;
    }

}

@@ -79,17 +79,16 @@
  Trie %7B%0A
-%0A
     priv
@@ -211,30 +211,32 @@
 Node node = 
-search
+traverse
 (word, true)
@@ -268,34 +268,8 @@
 rue;
- /* node cannot be null */
 %0A   
@@ -337,22 +337,24 @@
  node = 
-search
+traverse
 (word, f
@@ -470,108 +470,47 @@
     
-TrieNode node = search(prefix, false);%0A        return node != null; // no need to do dfs search here
+return traverse(prefix, false) != null;
 %0A   
@@ -534,22 +534,24 @@
 rieNode 
-search
+traverse
 (String 
@@ -564,19 +564,17 @@
 boolean 
-isC
+c
 reate) %7B
@@ -595,20 +595,19 @@
 ode 
-node
+cur
  = root;
  /* 
@@ -606,84 +606,8 @@
 oot;
- /* invariant: node correspond to word%5Bi-1%5D =%3E entire word when terminate */
 %0A   
@@ -713,29 +713,24 @@
     if (
-node.children
+cur.next
 %5Bidx%5D ==
@@ -762,87 +762,76 @@
 if (
-isC
+!c
 reate) 
-node.children%5Bidx%5D = new TrieNode();%0A                else return null
+return null;%0A                cur.next%5Bidx%5D = new TrieNode()
 ;%0A  
@@ -858,28 +858,22 @@
     
-node = node.children
+cur = cur.next
 %5Bidx
@@ -900,20 +900,19 @@
  return 
-node
+cur
 ;%0A    %7D%0A
@@ -920,36 +920,22 @@
     
-private boolean dfs(
+class 
 TrieNode
  nod
@@ -934,14 +934,8 @@
 Node
- node)
  %7B%0A 
@@ -945,170 +945,68 @@
     
-if (node == null) return false;%0A        if (node.isWord) return true;%0A        for (TrieNode n : node.children)%0A            if (dfs(n)) return true;%0A        return
+TrieNode%5B%5D next = new TrieNode%5B26%5D;%0A        boolean isWord =
  fal
@@ -1015,11 +1015,10 @@
 ;%0A    %7D%0A
-%0A
 %7D%0A

implement Trie