LeetCode #211: Design Add and Search Words Data Structure

https://leetcode.com/problems/design-add-and-search-words-data-structure/

The “Design Add and Search Words Data Structure” problem on LeetCode asks us to implement a data structure that can add words and search for words that match a given pattern, where the pattern can contain any character represented by ‘.’. To solve this problem, we can use a hash table to store the words based on their length. Each key in the hash table will be a length of a word and the value will be a set of all words that have that length.

To add a word, we simply add it to the set of words with the same length. To search for a word, we first check if the word is in the set of words with the same length. If the word contains the ‘.’ character, we iterate over all the words in the set with the same length and compare their characters to the pattern. We check for a match by comparing each character in the pattern to the corresponding character in the word from the set. If the character in the pattern is not ‘.’, then it must match the character in the word from the set. If there is a mismatch, we move on to the next word in the set. If we find a word that matches the pattern, we return True. If we have searched all the words in the set with the same length and none of them match the pattern, we return False.

Here’s the Python solution:

import collections

class WordDictionary(object):
    def __init__(self):
        self.word_dict = collections.defaultdict(set)

    def addWord(self, word):
        if word:
            self.word_dict[len(word)].add(word)

    def search(self, word):
        if not word:
            return False
        
        if '.' not in word:
            return word in self.word_dict[len(word)]
        
        for v in self.word_dict[len(word)]:
            for i, ch in enumerate(word):
                if ch != v[i]:
                    if ch != '.':
                        break
            else:
                return True
        return False

Time and Space Complexity

The time complexity of adding a word to the data structure is O(1). The time complexity of searching for a word is O(n * m), where n is the number of words with the same length as the pattern and m is the length of the pattern. The space complexity of the data structure is O(n * m), where n is the number of words and m is the maximum length of the words.