Add and Search for a Word — Data Structure Design

4 min readAug 6, 2020

I’m just happy as a pig in py…..cuz my answer scored super high in speed and low memory usage today for the daily Leetcode Challenge.

Challenge Information

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

My Solution:

class WordDictionary:
    from collections import defaultdict
    import re
    
    def __init__(self):
        self.wordDict = defaultdict(list)
        
    def addWord(self, word: str):
        self.wordDict[len(word)].append(word)    def search(self, word: str):
        wordLen = len(word)
        
        if '.' not in word:
            return word in self.wordDict[wordLen]
        
        pattern = word.replace('.','[a-z]')
        regex = re.compile(pattern)
        for w in self.wordDict[wordLen]:
            if regex.match(w) is not None:
                return True
            
        return False

Solution Explanation

I imported from two python modules for this challenge, defaultdict and re.

defaultdict

I imported the defaultdict container from the collections module, instead of using the standard dictionary that’s part of the base language. defaultdictdoesn’t throw a KeyError when a key doesn’t exist. Instead, it creates the key with a default value. Among other benefits, this removes the need to use a try/except or a if/else statement, first checking for a key, and then adding it, if it doesn’t exist. The addWord function is shorter because of that.

https://www.accelebrate.com/blog/using-defaultdict-python has some examples of using defaultdict and a short/sweet explanation of a few reasons why they’re a good choice.

`re`

re is the regex module for Python. I use it in this part of the code:

   pattern = word.replace('.','[a-z]')
   regex = re.compile(pattern)
   for w in self.wordDict[wordLen]:
       if regex.match(w) is not None:
           return True

The pattern portion of it says that any single dot can be replaces with a single character a-z. The challenge information said: “A . means it can represent any one letter.”

The pattern definition would cause a search for ‘b..’ to match the word ‘bad’ in the dictionary. And if the pattern were ‘.ad’, in the example above, that would cause a match on bad, dad, and mad.

Another way to think about it is that this particular pattern definition turned the ‘.’ into a single character wildcard for any character a-z.

I usedre.compile instead of re.match, because the pattern could be used repeatedly. re.compile compiles the pattern in advance, which makes looking for a match faster.

ProgramCreek has 40 code examples for re.compile() if you’re interested in learning more.

When the words get added, their length is used to determine what list they get added to in the dictionary.

For example, if I added the words “friend”, “lettuce”, “go”, “to” “the” “beach”, to the dictionary, here’s what it would look like:

defaultdict(<class 'list'>, {6: ['friend'], 7: ['lettuce'], 2: ['go', 'to'], 3: ['the'], 5: ['beach']})

Each item is stored in a list by its length. “go” and “to” ended up in the same list.

Results

My solution was 98.08% faster than other submissions and used less memory than 92% of the other submissions.

However….There was a hint link between the challenge and the code editor. I’ve always thought those to be hints when I’m stuck…rather than extra information about the problem.

Today was different, at least to me. The hint was “You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.”

Oops. Well, I didn’t use a Trie. I’m so happy with my result percentage that I’m just going to tell myself if it was a requirement to use a Trie, they would have put that in the main part of the problem statement…right?!

In any case, now that I’ve seen the hint…I AM going to TRY it tomorrow with a TRIE structure (pronounced like ‘tree’).

In the meantime, I’m going to sleep with a smile on my face, cuz I’m pretty proud of what I DID submit.