Design Add and Search Words Data Structure
MedPrompt
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)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay 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 <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsist of'.'or lowercase English letters.- There will be at most
2dots inwordforsearchqueries. - At most
104calls will be made toaddWordandsearch.
Approaches
2 approaches with complexity analysis and trade-offs.
Store all words in an ArrayList and perform linear search during search operation. For dots, check each character position individually.
Algorithm
- Initialize an ArrayList to store words
- For addWord:
- Add the word to the ArrayList
- 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
Walkthrough
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.
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; }}Complexity
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
Trade-offs
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
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.
Algorithm
- Create a TrieNode class with children array and isEndOfWord flag
- For addWord:
- Start from root node
- For each character, create or traverse to child node
- Mark last node as end of word
- 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
Walkthrough
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.
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); } }}Complexity
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
Trade-offs
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
Solutions
Solution
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 ); } }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); */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); */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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.