# Add and Search Word

Design a data structure that supports the following two operations:

```java
void addWord(word)
boolean search(word)
```

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

```
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
```

Note:\
You may assume that all words are consist of lowercase letters a-z.

## Analysis

在Implement Trie的基础之上，应用Trie。不同之处在于对于pattern的匹配，需要进行backtracking，也就是利用DFS，对于匹配了'.'的那个TrieNode的每一个children都循环遍历，如果有一个为true，则说明找到一个match，即可返回true。

## Solution

```java
class TrieNode {
    public boolean isLeaf;
    public TrieNode[] children;

    public TrieNode() {
        this.children = new TrieNode[26];
    }
}

public class WordDictionary {

    private TrieNode root;

    public WordDictionary() {
        this.root = new TrieNode();
    }

    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode p = this.root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (p.children[index] == null) {
                TrieNode temp = new TrieNode();
                p.children[index] = temp;
            }
            p = p.children[index];
        }
        p.isLeaf = 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 match(this.root, word, 0);
    }

    private boolean match(TrieNode p, String word, int k) {
        if (k == word.length()) {
            return p.isLeaf;
        }
        if (word.charAt(k) == '.') {
            for (int i = 0; i < p.children.length; i++) {
                if (p.children[i] != null) {
                    if (match(p.children[i], word, k + 1)) {
                        return true;
                    }
                }
            }
        } else {
            int index = word.charAt(k) - 'a';
            return p.children[index] != null && match(p.children[index], word, k + 1);
        }
        return false;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
```

(126ms 54.49%)

```java
class WordDictionary {
    public class TrieNode {
        private TrieNode[] children;
        private boolean isEnd;
        public TrieNode() {
            children = new TrieNode[26];
        }
        public TrieNode[] getChildren() {
            return children;
        }
        public boolean containsKey(char ch) {
            return children[ch - 'a'] != null;
        }
        public TrieNode get(char ch) {
            return children[ch - 'a'];
        }
        public void put(char ch, TrieNode node) {
            children[ch - 'a'] = node;
        }
        public void setEnd() {
            isEnd = true;
        }
        public boolean isEnd() {
            return isEnd;
        }
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd();
    }

    /** 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 match(word, 0, root);
    }

    private boolean match(String word, int index, TrieNode node) {
        if (index == word.length()) return node.isEnd();

        char currentChar = word.charAt(index);
        if (currentChar == '.') {
            TrieNode[] children = node.getChildren();
            for (int i = 0; i < children.length; i++) {
                if (children[i] != null && match(word, index + 1, children[i])) {
                    return true;
                };
            }
        } else {
            return node.get(currentChar) != null && match(word, index + 1, node.get(currentChar));
        }
        return false;
    } 
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
```

## Reference

* [LeetCode Discuss](https://discuss.leetcode.com/topic/14030/my-simple-and-clean-java-code)
* [ProgramCreek Solution](http://www.programcreek.com/2014/05/leetcode-add-and-search-word-data-structure-design-java/)
* [Jiuzhang Solution](http://www.jiuzhang.com/solutions/add-and-search-word/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/trie/add_and_search_word.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.