Leetcode Daily - August 5, 2020

Add and Search Data Structure

Link to the Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

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 Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Store words in an array

(Submission - Time Exceeded)

I added wordList Array to the WordDictionary class. Then the add method simply pushes the word to the Array. I even checked if the Array already included the word to make sure I didn't have duplicates.

This made the search method pretty challenging. If an exact word is given, I could simply use Array.includes. But for optional letters indicated by the '.', I had to first iterate through an array then iterate through the letters of the word. There is probably a smarter way to do this, for example, with regex, but I ended up getting 'time exceeded' on my submission.

Attempt 2 - Changing data structure to a Hash table

(Submission - Accepted)

Since Hash tables are virtually O(1) for data retrieval I decided I would stop using the Array and use a Hash table.

However, simply using the word as the key would not make it any easier to retrieve words that had to match optional letters, '.'. I decided to refactor my data structure to make searching easier, but adding would be slightly harder.

My data structure is a hash table that has the following key value pairs:

• key - length of word (maybe prepended with 'len' or another string)
• value - Array of words

My add function checks if the key named len${word.length} exists, and if it does, it pushes the word to the Array held by that key. If the key does not exist, it is created with the value [word].

My search function checks if the key named len${word.length} exists, and if it does then it iterates through the array and tries to match the letters of the searched word. This is actually very similar to the original array implementation, but the array searched is potentially much smaller, unless all or most of the words in the dictionary are the same length.

This ended up being my accepted submission.

Discussion and Conclusion

I still have to do some studying on the optimal implementation of this problem. I feel that if I designed a better data structure then perhaps there could be a more efficient search algorithm. But of course, there could potentially be added complexity to the add algorithm.

In my current solution, add should still be O(1) if you ignore any complexities of using the Array.push method. And, search should still be O(n), because even though we broke down our storage data structure by word length, the amount of words stored and therefore the iterative search time still grows proportionally to the number of words added.