Design Add and Search Words Data Structure
Problem 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)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
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.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
We can store each added word in a list and when a search operation is called, we'll iterate through all the stored words to check if there's any match to the search word. For search words having a wildcard character '.', we need to check each character except the wildcard positions. This approach is inefficient for large datasets due to the linear search which is coupled with string matching complexity.
Code:
- Time Complexity: O(n * m) for search where n is the number of words and m is the average length of words.
- Space Complexity: O(n) to store the list of words.
2. Trie Implementation
Intuition:
A more efficient approach is to use a Trie (prefix tree) to store the added words. The trie allows us to efficiently search by traversing down the tree character by character, matching the structure of the search word. For each wildcard '.', we can traverse down all possible paths. This significantly reduces the time complexity for search operations compared to the brute force method.
Code:
- Time Complexity: O(m) for adding and typical search where m is the length of the word.
- Space Complexity: O(n * m) where n is the number of words and m is the average length of words to store the Trie.