> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/201-300/design-add-and-search-words-data-structure.md).

# 211. Design Add and Search Words Data Structure

### Description

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the `WordDictionary` class:

* `WordDictionary()` Initializes the object.
* `void addWord(word)` Adds `word` to the data structure, it can be matched later.
* `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter.

### Constraints

* `1 <= word.length <= 500`
* `word` in `addWord` consists lower-case English letters.
* `word` in `search` consist of  `'.'` or lower-case English letters.
* At most `50000` calls will be made to `addWord` and `search`.

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/design-add-and-search-words-data-structure/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-add-and-search-word-data-structure-design-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:**

\["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search"]

\[\[], \["bad"], \["dad"], \["mad"], \["pad"], \["bad"], \[".ad"], \["b.."]]

**Output:**

\[null, null, null, null, false, true, true, true]

**Explanation:**

WordDictionary wordDictionary = new WordDictionary();

wordDictionary.addWord("bad");

wordDictionary.addWord("dad");

wordDictionary.addWord("mad");

wordDictionary.search("pad"); // return False

wordDictionary.search("bad"); // return True

wordDictionary.search(".ad"); // return True

wordDictionary.search("b.."); // return True
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(M), where M is the key length. At each 
 *    step, we either examine or create a node in the trie. 
 *    That takes only M operations.
 * Space complexity : O(M). In the worst-case newly inserted 
 *    key doesn't share a prefix with the keys already 
 *    inserted in the trie. We have to add M new nodes, 
 *    which takes O(M) space.
 */

class WordDictionary {
    private Map<Integer, Set<String>> dict;

    /** Initialize your data structure here. */
    public WordDictionary() {
        dict = new HashMap();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        int m = word.length();
        if(!dict.containsKey(m)) {
            dict.put(m, new HashSet());
        }
        dict.get(m).add(word);
    }
    
    /** 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) {
        int m = word.length();
        if(dict.containsKey(m)) {
            for(String w: dict.get(m)) {
                int i = 0;
                while(i < m && 
                        (w.charAt(i) == word.charAt(i) || 
                        word.charAt(i) == '.')) {
                    i++;
                }
                if(i == m) return true;
            }
        }
        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);
 */
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class TrieNode {
    Map<Character, TrieNode> children = new HashMap();
    boolean word = false;
    public TrieNode() {}
}

class WordDictionary {
    TrieNode trie;

    /** Initialize your data structure here. */
    public WordDictionary() {
        trie = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode node = trie;
        
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                node.children.put(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.word = true;
    }
    
    /** Returns if the word is in the node. */
    public boolean searchInNode(String word, TrieNode node) {
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if (!node.children.containsKey(ch)) {
                // if the current character is '.'
                // check all possible nodes at this level
                if (ch == '.') {
                    for (char x : node.children.keySet()) {
                        TrieNode child = node.children.get(x);
                        if (searchInNode(word.substring(i + 1), child)) {
                            return true;    
                        }    
                    }   
                }
                // if no nodes lead to answer
                // or the current character != '.'
                return false;    
            } else {
                // if the character is found
                // go down to the next level in trie
                node = node.children.get(ch); 
            }   
        }      
        return node.word;
    }

    /** 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 searchInNode(word, trie);
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*