@@ -0,0 +1,2277 @@
+package addAndSearchWord;%0A%0Aimport java.util.*;%0A%0Aclass TrieNode%7B%0A    char val;%0A    boolean isLeaf;%0A    Map%3CCharacter, TrieNode%3E children;%0A    TrieNode(char c) %7B%0A        this.val = c;%0A        isLeaf = false;%0A        children = new HashMap%3CCharacter, TrieNode%3E();%0A    %7D%0A%7D%0A%0Apublic class WordDictionary %7B%0A    TrieNode root;%0A    %0A    public WordDictionary()%7B%0A        this.root = new TrieNode(' ');%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    public void addWord(TrieNode root, String word, int index)%7B%0A        if(index %3E= word.length()) return;%0A        %0A        if(!root.children.containsKey(word.charAt(index)))%7B%0A            root.children.put(word.charAt(index), new TrieNode(word.charAt(index)));%0A        %7D%0A        %0A        if(index == word.length()-1)%7B%0A            root.children.get(word.charAt(index)).isLeaf = true;%0A            return;%0A        %7D%0A        addWord(root.children.get(word.charAt(index)), word, index+1);%0A    %7D%0A%0A    // Returns if the word is in the data structure. A word could%0A    // contain the dot character '.' to represent any one letter.%0A    public boolean search(String word) %7B%0A        return search(root, word, 0);%0A    %7D%0A    %0A    @SuppressWarnings(%22rawtypes%22)%0A%09public boolean search(TrieNode root, String word, int index)%7B%0A        if(index %3E= word.length()) return false;%0A        char c = word.charAt(index);%0A        if(c == '.')%7B%0A            Iterator it = root.children.entrySet().iterator();%0A            while(it.hasNext())%7B%0A                Map.Entry entry = (Map.Entry) it.next();%0A                TrieNode child = (TrieNode) entry.getValue();%0A                if(index == word.length() -1 && child.isLeaf) return true;%0A                if(search(child, word, index+1)) return true;%0A            %7D%0A            return false;%0A        %7Delse if(root.children.containsKey(c))%7B%0A            if(index == word.length() -1 && root.children.get(c).isLeaf) return true;%0A            return search(root.children.get(c), word, index+1);%0A        %7D%0A        return false;%0A    %7D%0A%7D%0A%0A// Your WordDictionary object will be instantiated and called as such:%0A// WordDictionary wordDictionary = new WordDictionary();%0A// wordDictionary.addWord(%22word%22);%0A// wordDictionary.search(%22pattern%22);

add and search word -- use trie prefix tree to implement data structure