package JiuChap3_DequeStackTrie;

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

/**
 * http://www.lintcode.com/en/problem/add-and-search-word/#
 * Created this class in JiuChap3_DequeStackTrie at 3:24 PM, 11/7/2015.
 */
public class AddSearchWord {

  public static void main(String[] args) {
    AddSearchWord asw = new AddSearchWord();
    asw.verify();
  }

  public void verify() {
    TrieTree trie = new TrieTree();
    //String[] words = new String[] { "to", "tea", "ted", "ten", "ind" };
    //for (String word : words) {
    //  trie.addWord(word);
    //}

    //System.out.println(trie.search("too"));
    //System.out.println(trie.search("tow"));
    //System.out.println(trie.search("tea"));
    //System.out.println(trie.search("te."));
    //System.out.println(trie.search(".nd"));

    //trie.addWord("a");
    //System.out.println(trie.search("."));

    trie.addWord("ran");
    trie.addWord("rune");
    trie.addWord("runner");
    trie.addWord("runs");
    trie.addWord("add");
    trie.addWord("adds");
    trie.addWord("adder");
    trie.addWord("addee");
    System.out.println(trie.search("r.n"));
    //System.out.println(trie.search("ru.n.e"));
    //System.out.println(trie.search("add"));
    //System.out.println(trie.search("add."));
    //System.out.println(trie.search("adde."));
    //System.out.println(trie.search(".an."));
    //System.out.println(trie.search("...s"));
    //System.out.println(trie.search("....e."));
    //System.out.println(trie.search("......."));
    //System.out.println(trie.search("..n.r"));
  }

  private class TrieNode {
    String s;
    Map<Character, TrieNode> subtree;
    boolean isString;

    public TrieNode() {
      s = "";
      subtree = new HashMap<>();
      isString = false;
    }
  }

  private class TrieTree {
    TrieNode root;

    private TrieTree(TrieNode node) {
      root = node;
    }

    public TrieTree() {
      this(new TrieNode());
    }

    // Adds a word into the data structure.
    public void addWord(String word) {
      // Write your code here
      TrieNode cur = root;
      for (int i = 0; i < word.length(); ++i) {
        char ch = word.charAt(i);
        if (!cur.subtree.containsKey(ch)) {
          cur.subtree.put(ch, new TrieNode());
        }
        cur = cur.subtree.get(ch);
      }
      cur.s = word;
      cur.isString = true;
    }

    // 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) {
      return find(word, 0, root);
    }

    /*
    // 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) {
      TrieNode cur = root;
      for (int i = 0; i < word.length(); ++i) {
        char ch = word.charAt(i);
        if (ch != '.' && cur.subtree.containsKey(ch)) {
          return false;
        } else if (cur.subtree.containsKey(ch)) {
          cur = cur.subtree.get(ch);
        } else {
          //for (TrieNode next : cur.subtree.values()) {
          //  cur = next;  // need to use recursion to search from this point, or use stack (not sure how)
          //}
        }
      }
    }
    */

    public boolean find(String word, int idx, TrieNode root) {
      if (idx == word.length() && root.isString) {
        return true;
      }

      boolean idxLevel = false;
      for (Character key : root.subtree.keySet()) {
        char ch = word.charAt(idx);
        if (ch == '.') {
          for (TrieNode nd : root.subtree.values()) {
            idxLevel |= find(word, idx + 1, nd);
          }
        } else {
          if (key != ch) {
            //return false;
            idxLevel |= false;
          } else {
            System.out.println("true at: " + ch + " index: " + idx);
            idxLevel |= find(word, idx + 1, root.subtree.get(ch));
          }
        }
      }
      return idxLevel;
    }

    public boolean find(String word) {
      // Write your code here
      TrieNode cur = root;
      for (int i = 0; i < word.length(); ++i) {
        char ch = word.charAt(i);
        if (!cur.subtree.containsKey(ch)) {
          return false;
        }
        cur = cur.subtree.get(ch);
      }
      return cur.isString;
    }
  }
}

@@ -422,18 +422,16 @@
 ();%0A    
-//
 String%5B%5D
@@ -490,26 +490,24 @@
 ind%22 %7D;%0A    
-//
 for (String 
@@ -526,18 +526,16 @@
 ) %7B%0A    
-//
   trie.a
@@ -552,18 +552,16 @@
 d);%0A    
-//
 %7D%0A%0A    /
@@ -781,11 +781,11 @@
 ch(%22
-.nd
+in.
 %22));
@@ -1106,34 +1106,32 @@
 ch(%22r.n%22));%0A    
-//
 System.out.print
@@ -1153,34 +1153,32 @@
 %22ru.n.e%22));%0A    
-//
 System.out.print
@@ -1197,34 +1197,32 @@
 ch(%22add%22));%0A    
-//
 System.out.print
@@ -1242,34 +1242,32 @@
 h(%22add.%22));%0A    
-//
 System.out.print
@@ -1288,34 +1288,32 @@
 (%22adde.%22));%0A    
-//
 System.out.print
@@ -1333,34 +1333,32 @@
 h(%22.an.%22));%0A    
-//
 System.out.print
@@ -1378,34 +1378,32 @@
 h(%22...s%22));%0A    
-//
 System.out.print
@@ -1425,34 +1425,32 @@
 %22....e.%22));%0A    
-//
 System.out.print
@@ -1473,34 +1473,32 @@
 .......%22));%0A    
-//
 System.out.print
@@ -3316,20 +3316,32 @@
 length()
- && 
+) %7B%0A        if (
 root.isS
@@ -3345,24 +3345,26 @@
 isString) %7B%0A
+  
         retu
@@ -3368,24 +3368,75 @@
 eturn true;%0A
+        %7D else %7B%0A          return false;%0A        %7D%0A
       %7D%0A%0A   
@@ -3780,24 +3780,15 @@
     
-idxLevel %7C= fals
+continu
 e;%0A 
@@ -3813,24 +3813,26 @@
             
+//
 System.out.p

add search word.