Design Add and Search Words Data Structure

MEDIUM

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.

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 10⁴ calls will be made to addWord and search.

Approaches

Checkout 2 different approaches to solve Design Add and Search Words Data Structure. Click on different approaches to view the approach and algorithm in detail.

Array/List Based Approach

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

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 Analysis

Time Complexity: O(N * L) where N is number of words and L is average length of words for search operation, O(1) for add operationSpace Complexity: O(N * L) where N is number of words and L is average length of words

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Design Add and Search Words Data Structure. Click on different languages to view the code.

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 ); } }

Video Solution

Watch the video walkthrough for Design Add and Search Words Data Structure

Algorithms:

Depth-First Search

Patterns:

Design

Data Structures:

StringTrie

Companies:

Atlassian |Docusign |DoorDash |LinkedIn |