package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/implement-trie-prefix-tree/
 */
public class Problem208 {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        char value;
        boolean complete;

        // Initialize your data structure here.
        public TrieNode() {
        }

        public TrieNode(char value) {
            this.value = value;
        }
    }

    public static class Trie {
        private TrieNode root;

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

        // Inserts a word into the trie.
        public void insert(String word) {
            insert(root, word, 0);
        }

        private void insert(TrieNode node, String word, int idx) {
            if (word.length() == idx) {
                node.complete = true;
                return;
            }
            char c = word.charAt(idx);
            TrieNode n;
            if (node.children.containsKey(c)) {
                n = node.children.get(c);
            } else {
                n = new TrieNode(c);
                node.children.put(c, n);
            }
            insert(n, word, idx + 1);
        }

        // Returns if the word is in the trie.
        public boolean search(String word) {
            return search(root, word, 0);
        }

        private boolean search(TrieNode node, String word, int idx) {
            if (node == null) {
                return false;
            }
            if (word.length() == idx) {
                if (node.complete) {
                    return true;
                }
                return false;
            }
            char c = word.charAt(idx);
            if (!node.children.containsKey(c)) {
                return false;
            }
            TrieNode n = node.children.get(c);
            return search(n, word, idx + 1);
        }

        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            return startsWith(root, prefix, 0);
        }

        private boolean startsWith(TrieNode node, String prefix, int idx) {
            if (node == null) {
                return false;
            }
            if (prefix.length() == idx) {
                return true;
            }
            char c = prefix.charAt(idx);
            if (!node.children.containsKey(c)) {
                return false;
            }
            TrieNode n = node.children.get(c);
            return startsWith(n, prefix, idx + 1);
        }
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -111,16 +111,23 @@
 8 %7B%0A    
+public 
 static c
@@ -139,47 +139,79 @@
 Trie
-Node %7B%0A        Map%3CCharacter, Trie
+ %7B%0A        private static class Node %7B%0A            private final 
 Node
-%3E
+%5B%5D
  chi
@@ -226,28 +226,37 @@
 new 
-HashMap%3C%3E();%0A       
+Node%5B26%5D;%0A            private
  cha
@@ -272,16 +272,28 @@
         
+    private 
 boolean 
@@ -311,52 +311,8 @@
     
-    // Initialize your data structure here.%0A
     
@@ -318,28 +318,24 @@
      public 
-Trie
 Node() %7B%0A   
@@ -327,24 +327,28 @@
 ic Node() %7B%0A
+    
         %7D%0A%0A 
@@ -354,27 +354,27 @@
         
+    
 public 
-Trie
 Node(cha
@@ -396,16 +396,20 @@
         
+    
 this.val
@@ -432,47 +432,24 @@
     
-%7D%0A
     %7D%0A
-%0A
     
-public static class Trie %7B
+    %7D%0A
 %0A   
@@ -461,20 +461,22 @@
 private 
-Trie
+final 
 Node roo
@@ -476,16 +476,29 @@
 ode root
+ = new Node()
 ;%0A%0A     
@@ -520,43 +520,8 @@
 ) %7B%0A
-            root = new TrieNode();%0A
     
@@ -672,16 +672,23 @@
 private 
+static 
 void ins
@@ -691,20 +691,16 @@
  insert(
-Trie
 Node nod
@@ -897,71 +897,41 @@
     
-Trie
 Node n
-;%0A            if (node.children.containsKey(c)) %7B%0A   
+ = node.children%5Bc - 'a'%5D;%0A
     
@@ -942,53 +942,22 @@
     
- 
+if (
 n =
+=
  n
-ode.children.get(c);%0A            %7D else
+ull)
  %7B%0A 
@@ -979,20 +979,16 @@
 n = new 
-Trie
 Node(c);
@@ -1021,18 +1021,21 @@
 dren
-.put(c,
+%5Bc - 'a'%5D =
  n
-)
 ;%0A  
@@ -1248,32 +1248,39 @@
         private 
+static 
 boolean search(T
@@ -1278,20 +1278,16 @@
  search(
-Trie
 Node nod
@@ -1441,28 +1441,31 @@
             
-if (
+return 
 node.complet
@@ -1469,91 +1469,8 @@
 lete
-) %7B%0A                    return true;%0A                %7D%0A                return false
 ;%0A  
@@ -1528,33 +1528,32 @@
             if (
-!
 node.children.co
@@ -1545,39 +1545,41 @@
 ode.children
-.containsKey(c)
+%5Bc - 'a'%5D == null
 ) %7B%0A        
@@ -1618,36 +1618,32 @@
   %7D%0A            
-Trie
 Node n = node.ch
@@ -1640,39 +1640,41 @@
  = node.children
-.get(c)
+%5Bc - 'a'%5D
 ;%0A            re
@@ -1958,20 +1958,16 @@
 rtsWith(
-Trie
 Node nod
@@ -2217,9 +2217,8 @@
 if (
-!
 node
@@ -2230,23 +2230,25 @@
 dren
-.containsKey(c)
+%5Bc - 'a'%5D == null
 ) %7B%0A
@@ -2303,20 +2303,16 @@
         
-Trie
 Node n =
@@ -2329,15 +2329,17 @@
 dren
-.get(c)
+%5Bc - 'a'%5D
 ;%0A  

Update problem 208