TIC
The Interns Company

Design Add and Search Words Data Structure

MediumAcceptance: 41.8%
StringDepth-First SearchDesignTrie

Problem Statement

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 <= 25
  • word in addWord consists of lowercase English letters.
  • word in search consist of '.' or lowercase English letters.
  • There will be at most 3 dots in word for search.
  • At most 10^4 calls will be made to addWord and search.

Input Format:

  • Commands to execute operations on WordDictionary data structure.

Output Format:

  • Results of operations performed on the WordDictionary data structure.

Examples:

Example 1:

Input:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],["..."],["..d"]]

Output:

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("..d"); // return True

Solutions

Trie with DFS Search

Time: O(M) for addWord and O(26^N) for search in the worst case, where M is the length of the word and N is the number of '.' characters
Space: O(M*N) where M is the total number of characters in all words and N is the number of words

Use a trie to store words and implement search with DFS to handle wildcard characters.

Array-based Trie Implementation

Time: O(M) for addWord and O(26^N) for search in the worst case, where M is the length of the word and N is the number of '.' characters
Space: O(M*26) where M is the total number of nodes in the trie

Use arrays instead of hash maps for the trie nodes to potentially improve performance for lowercase English letters.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize a new WordDictionary with an empty root node
  2. Add "bad":
  3. Create trie nodes for 'b', 'a', 'd'
  4. Mark the node for 'd' as the end of a word
  5. Add "dad":
  6. Create trie node for 'd' (first letter)
  7. Reuse node for 'a' (second letter)
  8. Reuse node for 'd' (third letter)
  9. Mark the node for 'd' as the end of a word
  10. Add "mad":
  11. Create trie node for 'm' (first letter)
  12. Reuse node for 'a' (second letter)
  13. Reuse node for 'd' (third letter)
  14. Mark the node for 'd' as the end of a word
  15. Search "pad":
  16. No trie node for 'p', return false
  17. Search "bad":
  18. Follow the path 'b' -> 'a' -> 'd'
  19. The node for 'd' is marked as the end of a word
  20. Return true
  21. Search ".ad":
  22. For '.', must check all children of the root
  23. Check 'b' -> 'a' -> 'd', the node for 'd' is marked as the end of a word, return true
  24. Search "..d":
  25. For the first '.', check all children of the root
  26. For the second '.', check all children of each first-level node
  27. Eventually find path 'b'/'d'/'m' -> 'a' -> 'd' where the final 'd' is marked as the end of a word
  28. Return true

Hints

Hint 1
Use a trie data structure to store the words for efficient prefix matching.
Hint 2
When searching with '.', you'll need to explore all possible characters at that position.
Hint 3
A recursive search approach can help handle wildcard characters.

Video Tutorial

Design Add and Search Words Data Structure - Trie with Wildcards

YouTube•Learn the Design Add and Search Words Data Structure solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the trie data structure and how words with wildcards are searched in it.

Key visualization elements:

  • current node
  • wildcard expansion
  • matching paths
  • end of word markers

Similar Questions

Implement Trie (Prefix Tree)

Medium

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Word Search II

Hard

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Asked By

FacebookAmazonGoogleMicrosoftBloombergTwitterSnapchat

Implementation Notes

This problem builds on the basic trie data structure by adding wildcard matching capability, making it more complex and powerful for word searching applications.