# Design Add and Search Words Data Structure
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-add-and-search-words-data-structure)
Canonical: https://scaleengineer.com/dsa/problems/design-add-and-search-words-data-structure
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** String, Trie
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Snowflake](https://scaleengineer.com/companies/snowflake), [Rubrik](https://scaleengineer.com/companies/rubrik), [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
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.

**Example:**

**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

**Constraints:**

* `1 <= word.length <= 25`
* `word` in `addWord` consists of lowercase English letters.
* `word` in `search` consist of `'.'` or lowercase English letters.
* There will be at most `2` dots in `word` for `search` queries.
* At most `104` calls will be made to `addWord` and `search`.

# Approaches
## Array/List Based Approach
Store all words in an ArrayList and perform linear search during search operation. For dots, check each character position individually.
**Time:** O(N * L) where N is number of words and L is average length of words for search operation, O(1) for add operation · **Space:** O(N * L) where N is number of words and L is average length of words
**Pros:** Simple implementation; Minimal space usage; Good for small datasets
**Cons:** Poor search performance for large datasets; Linear search time; Not scalable for large number of words
### Explanation
In this approach, we maintain a simple ArrayList to store all the words. When adding a word, we simply append it to the list. For searching, we need to check each word in the list and compare it with the search pattern.

For exact word matches, we can use string comparison. For patterns containing dots, we need to check each character position, where a dot can match any character.

```java
class WordDictionary {
    private List<String> words;
    
    public WordDictionary() {
        words = new ArrayList<>();
    }
    
    public void addWord(String word) {
        words.add(word);
    }
    
    public boolean search(String word) {
        for (String storedWord : words) {
            if (storedWord.length() != word.length()) continue;
            
            boolean matches = true;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) != '.' && word.charAt(i) != storedWord.charAt(i)) {
                    matches = false;
                    break;
                }
            }
            if (matches) return true;
        }
        return false;
    }
}
```
### Algorithm
1. Initialize an ArrayList to store words
2. For addWord:
   - Add the word to the ArrayList
3. For search:
   - Iterate through all stored words
   - For each word, check if length matches
   - Compare each character, treating '.' as wildcard
   - Return true if any word matches, false otherwise

## Trie Based Approach
Use a Trie (prefix tree) data structure to store the words efficiently. Each node in the trie represents a character, and paths from root to leaf form complete words.
**Time:** O(L) for addWord where L is word length, O(26^d * L) for search where d is number of dots · **Space:** O(N * L) where N is total number of characters in all words
**Pros:** Efficient space usage for words with common prefixes; Fast exact word searches; Optimal for prefix-based operations; Scalable for large datasets
**Cons:** More complex implementation; Higher initial memory overhead; Search time increases exponentially with number of dots
### Explanation
A Trie is an efficient data structure for storing and searching strings. Each node in the trie contains a character and links to child nodes. When searching with dots, we can explore all possible paths at that position.

```java
class WordDictionary {
    class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;
        
        TrieNode() {
            children = new TrieNode[26];
            isEndOfWord = false;
        }
    }
    
    private TrieNode root;
    
    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        return searchInNode(word, 0, root);
    }
    
    private boolean searchInNode(String word, int index, TrieNode node) {
        if (index == word.length()) {
            return node.isEndOfWord;
        }
        
        char ch = word.charAt(index);
        if (ch == '.') {
            for (TrieNode child : node.children) {
                if (child != null && searchInNode(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            int childIndex = ch - 'a';
            TrieNode child = node.children[childIndex];
            if (child == null) return false;
            return searchInNode(word, index + 1, child);
        }
    }
}
```
### Algorithm
1. Create a TrieNode class with children array and isEndOfWord flag
2. For addWord:
   - Start from root node
   - For each character, create or traverse to child node
   - Mark last node as end of word
3. For search:
   - Use recursive DFS to explore paths
   - For '.', try all possible children
   - For regular characters, follow specific path
   - Return true if word is found

# Solutions
### CSharp

```csharp
using System.Collections.Generic ; using System.Linq ; class TrieNode { public bool IsEnd { get ; set ; } public TrieNode [] Children { get ; set ; } public TrieNode () { Children = new TrieNode [ 26 ]; } } public class WordDictionary { private TrieNode root ; public WordDictionary () { root = new TrieNode (); } public void AddWord ( string word ) { var node = root ; for ( var i = 0 ; i < word . Length ; ++ i ) { TrieNode nextNode ; var index = word [ i ] - 'a' ; nextNode = node . Children [ index ]; if ( nextNode == null ) { nextNode = new TrieNode (); node . Children [ index ] = nextNode ; } node = nextNode ; } node . IsEnd = true ; } public bool Search ( string word ) { var queue = new Queue < TrieNode >(); queue . Enqueue ( root ); for ( var i = 0 ; i < word . Length ; ++ i ) { var count = queue . Count ; while ( count -- > 0 ) { var node = queue . Dequeue (); if ( word [ i ] == '.' ) { foreach ( var nextNode in node . Children ) { if ( nextNode != null ) { queue . Enqueue ( nextNode ); } } } else { var nextNode = node . Children [ word [ i ] - 'a' ]; if ( nextNode != null ) { queue . Enqueue ( nextNode ); } } } } return queue . Any ( n => n . IsEnd ); } }
```

### Java

```java
class Trie { Trie [] children = new Trie [ 26 ]; boolean isEnd ; } class WordDictionary { private Trie trie ; /** Initialize your data structure here. */ public WordDictionary () { trie = new Trie (); } public void addWord ( String word ) { Trie node = trie ; for ( char c : word . toCharArray ()) { int idx = c - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; } node . isEnd = true ; } public boolean search ( String word ) { return search ( word , trie ); } private boolean search ( String word , Trie node ) { for ( int i = 0 ; i < word . length (); ++ i ) { char c = word . charAt ( i ); int idx = c - 'a' ; if ( c != '.' && node . children [ idx ] == null ) { return false ; } if ( c == '.' ) { for ( Trie child : node . children ) { if ( child != null && search ( word . substring ( i + 1 ), child )) { return true ; } } return false ; } node = node . children [ idx ]; } return node . isEnd ; } } /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */
```

### CPP

```cpp
class trie { public: vector < trie *> children ; bool is_end ; trie () { children = vector < trie *> ( 26 , nullptr ); is_end = false ; } void insert ( const string & word ) { trie * cur = this ; for ( char c : word ) { c -= 'a' ; if ( cur -> children [ c ] == nullptr ) { cur -> children [ c ] = new trie ; } cur = cur -> children [ c ]; } cur -> is_end = true ; } }; class WordDictionary { private: trie * root ; public: WordDictionary () : root ( new trie ) {} void addWord ( string word ) { root -> insert ( word ); } bool search ( string word ) { return dfs ( word , 0 , root ); } private: bool dfs ( const string & word , int i , trie * cur ) { if ( i == word . size ()) { return cur -> is_end ; } char c = word [ i ]; if ( c != '.' ) { trie * child = cur -> children [ c - 'a' ]; if ( child != nullptr && dfs ( word , i + 1 , child )) { return true ; } } else { for ( trie * child : cur -> children ) { if ( child != nullptr && dfs ( word , i + 1 , child )) { return true ; } } } return false ; } }; /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary* obj = new WordDictionary(); * obj->addWord(word); * bool param_2 = obj->search(word); */
```

### Python

```python
class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . is_end = False class WordDictionary : def __init__ ( self ): self . trie = Trie () def addWord ( self , word : str ) -> None : node = self . trie for c in word : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . is_end = True def search ( self , word : str ) -> bool : def search ( word , node ): for i in range ( len ( word )): c = word [ i ] idx = ord ( c ) - ord ( 'a' ) if c != '.' and node . children [ idx ] is None : return False if c == '.' : for child in node . children : if child is not None and search ( word [ i + 1 :], child ): return True return False node = node . children [ idx ] return node . is_end return search ( word , self . trie ) # Your WordDictionary object will be instantiated and called as such: # obj = WordDictionary() # obj.addWord(word) # param_2 = obj.search(word)
```