package leetcode;

/**
 * https://leetcode.com/problems/add-and-search-word-data-structure-design/
 */
public class Problem211 {
    public static class WordDictionary {
        // Adds a word into the data structure.
        public void addWord(String word) {
            // TODO
        }

        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        public boolean search(String word) {
            // TODO
            return false;
        }
    }

    public static void main(String[] args) {

    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -224,110 +224,987 @@
     
-// Adds a word into the data structure.%0A        public void addWord(String word) %7B%0A            // TODO
+private Node root = new Node();%0A%0A        private static class Node %7B%0A            char ch;%0A            boolean done;%0A            Map%3CCharacter, Node%3E children = new HashMap%3C%3E();%0A%0A            public Node() %7B%0A            %7D%0A%0A            public Node(char ch, boolean done) %7B%0A                this.ch = ch;%0A                this.done = done;%0A            %7D%0A        %7D%0A%0A        // Adds a word into the data structure.%0A        public void addWord(String word) %7B%0A            addWord(root, word, 0);%0A        %7D%0A%0A        private void addWord(Node node, String word, int idx) %7B%0A            if (idx == word.length()) %7B%0A                node.done = true;%0A                return;%0A            %7D%0A            char ch = word.charAt(idx);%0A            Node n;%0A            if (node.children.containsKey(ch)) %7B%0A                n = node.children.get(ch);%0A            %7D else %7B%0A                n = new Node(ch, false);%0A                node.children.put(ch, n);%0A            %7D%0A            addWord(n, word, idx+1);
 %0A   
@@ -1412,15 +1412,37 @@
     
-// TODO
+return search(root, word, 0);
 %0A   
@@ -1450,23 +1450,148 @@
     
+%7D%0A%0A
     
-return fals
+    private boolean search(Node node, String word, int idx) %7B%0A            if (idx == word.length()) %7B%0A                return node.don
 e;%0A 
@@ -1601,62 +1601,546 @@
     
+  
+  
 %7D%0A    
-%7D%0A%0A    public static void main(String%5B%5D args) %7B%0A
+        char ch = word.charAt(idx);%0A            if (!node.children.containsKey(ch)) %7B%0A                if (ch == '.') %7B%0A                    boolean found = false;%0A                    for (Map.Entry%3CCharacter, Node%3E e : node.children.entrySet()) %7B%0A                        found %7C= search(e.getValue(), word, idx+1);%0A                    %7D%0A                    return found;%0A                %7D%0A                return false;%0A            %7D%0A            Node n = node.children.get(ch);%0A            return search(n, word, idx+1);%0A        %7D
 %0A   

Solve problem 211