package leetcode;

/**
 * https://leetcode.com/problems/implement-trie-prefix-tree/
 */
public class Problem208 {
    static class TrieNode {
        // Initialize your data structure here.
        public TrieNode() {
            
        }
    }

    public static class Trie {
        private TrieNode root;

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

        // Inserts a word into the trie.
        public void insert(String word) {
            // TODO: implement this
        }

        // Returns if the word is in the trie.
        public boolean search(String word) {
            // TODO: implement this
            return false;
        }

        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            // TODO: implement this
            return false;
        }
    }
    
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("something");
        System.out.println(trie.search("something"));
        System.out.println(trie.search("some"));
        System.out.println(trie.search("blah"));
        System.out.println(trie.startsWith("some"));
        System.out.println(trie.startsWith("foo"));
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -180,24 +180,140 @@
  TrieNode %7B%0A
+        Map%3CCharacter, TrieNode%3E children = new HashMap%3C%3E();%0A        char value;%0A        boolean complete;%0A        %0A
         // I
@@ -380,28 +380,104 @@
 ) %7B%0A        
+%7D%0A
     
+    %0A        public TrieNode(char value) %7B%0A            this.value = value;
 %0A        %7D%0A 
@@ -714,195 +714,1237 @@
     
-// TODO: implement this%0A        %7D%0A%0A        // Returns if the word is in the trie.%0A        public boolean search(String word) %7B%0A            // TODO: implement this%0A            return false
+insert(root, word, 0);%0A        %7D%0A        %0A        private void insert(TrieNode node, String word, int idx) %7B%0A            if (word.length() == idx) %7B%0A                node.complete = true;%0A                return;%0A            %7D%0A            char c = word.charAt(idx);%0A            TrieNode n;%0A            if (node.children.containsKey(c)) %7B%0A                n = node.children.get(c);%0A            %7D else %7B%0A                n = new TrieNode(c);%0A                node.children.put(c, n);%0A            %7D%0A            insert(n, word, idx+1);%0A        %7D%0A%0A        // Returns if the word is in the trie.%0A        public boolean search(String word) %7B%0A            return search(root, word, 0);%0A        %7D%0A        %0A        private boolean search(TrieNode node, String word, int idx) %7B%0A            if (node == null) %7B%0A                return false;%0A            %7D%0A            if (word.length() == idx) %7B%0A                if (node.complete) %7B%0A                    return true;%0A                %7D%0A                return false;%0A            %7D%0A            char c = word.charAt(idx);%0A            if (!node.children.containsKey(c)) %7B%0A                return false;%0A            %7D%0A            TrieNode n = node.children.get(c);%0A            return search(n, word, idx+1)
 ;%0A  
@@ -2117,35 +2117,171 @@
     
-// TODO: implement this%0A   
+return startsWith(root, prefix, 0);%0A        %7D%0A        %0A        private boolean startsWith(TrieNode node, String prefix, int idx) %7B%0A            if (node == null) %7B%0A
     
@@ -2277,32 +2277,39 @@
 ull) %7B%0A         
+       
 return false;%0A  
@@ -2310,26 +2310,24 @@
 se;%0A        
-%7D%0A
     %7D%0A    %0A 
@@ -2328,376 +2328,328 @@
     
-%0A
     
-public static void main(String%5B%5D args) %7B%0A        Trie trie = new Trie();%0A        trie.insert(%22something%22);%0A        System.out.println(trie.search(%22something%22));%0A        System.out.println(trie.search(%22some%22));%0A        System.out.println(trie.search(%22blah%22));%0A        System.out.println(trie.startsWith(%22some%22));%0A        System.out.println(trie.startsWith(%22foo%22));
+    if (prefix.length() == idx) %7B%0A                return true;%0A            %7D%0A            char c = prefix.charAt(idx);%0A            if (!node.children.containsKey(c)) %7B%0A                return false;%0A            %7D%0A            TrieNode n = node.children.get(c);%0A            return startsWith(n, prefix, idx+1);%0A        %7D
 %0A   

Solve problem 208