Scale Engineer

Design Add and Search Words Data Structure

Med
#0199Time: O(N * L) where N is number of words and L is average length of words for search operation, O(1) for add operationSpace: O(N * L) where N is number of words and L is average length of words7 companies
Patterns
Design
Algorithms
Depth-First Search
Data structures
StringTrie
Companies
AtlassianDocusignDoorDashLinkedIn

Prompt

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

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

  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

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

Solutions

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

← Previous

Previous problem

Next →

Next problem