Design Add and Search Words Data Structure

Try to solve the Design Add and Search Words Data Structure problem.

We'll cover the following

Statement#

Design a data structure called WordDictionary that supports the following functionalities:

  • Constructor: This function will initialize the object.

  • Add Word(word): This function will store the provided word in the data structure.

  • Search Word(word): This function will return TRUE if any string in the WordDictionary object matches the query word. Otherwise, it will return FALSE. If the query word contains dots, ., each dot is free to match any letter of the alphabet.

    For example, the dot in the string “.ad” can have 2626 possible search results like “aad”, “bad”, “cad”, and so on.

  • Get Words(): This function will return all the words in the WordDictionary class.

Constraints:

  • 1≤1 \leq word.length ≤25\leq 25

  • Words passed to Add Word() consist of lowercase English letters.

  • Words passed to Search Word() consist of . or lowercase English letters.

  • There will be, at most, three dots in a word passed to Search Word().

  • At most, 10310^3 calls will be made to Add Word() , Get Words() and Search Word().

Examples#

Created with Fabric.js 3.6.6 Output dictionary bin add word("bin") Sample example 1Input

1 of 8

Created with Fabric.js 3.6.6 Output add word("data") dictionary bin data Sample example 2Input

2 of 8

Created with Fabric.js 3.6.6 Output true dictionary bin data search word("bin") Sample example 3Input

3 of 8

Created with Fabric.js 3.6.6 false dictionary bin data Output search word("bi") Sample example 4Input

4 of 8

Created with Fabric.js 3.6.6 dictionary bin data Output true search word(".in") Sample example 5Input

5 of 8

Created with Fabric.js 3.6.6 false dictionary bin data Output search word(".n") Sample example 6Input

6 of 8

Created with Fabric.js 3.6.6 dictionary bin data Output Sample example 7Input search word("d.t.") true

7 of 8

Created with Fabric.js 3.6.6 get words() bin data dictionary bin data Output Sample example 8Input

8 of 8

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Design Add and Search Words Data Structure

1

Consider the list [“bin”, “pin”, “spin”, “pint”]. What will be the output of Search Word(“bin”)?

A)

True

B)

False

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: The game below is only for the Add Word(word) function.

Drag and drop the cards to rearrange them in the correct sequence.

Start from the root node of the trie, and traverse the word one character at a time.

Calculate the index of the character between 1 and 26, and check whether the character already exists in the trie.

If the character is not present in the trie, then create a new trie node for it, otherwise use the existing trie node for this character.

Once all the characters of the current word are added to the trie, set a boolean variable to TRUE, marking this as the end of the word.

If we’ve reached the end of the word and the boolean flag is already set, this means that it is already present in the dictionary, so we return TRUE.

Try it yourself#

Implement your solution in word_dictionary.py in the following coding playground. You will need the provided supporting code to implement your solution. We have also provided a useful code template that you may build on to solve this problem.

Python
word_dictionary.py
trie.py
trie_node.py
dfs.py
Input #1
Input #2
Design Add and Search Words Data Structure

Solution: Search Suggestions System

Solution: Design Add and Search Words Data Structure