Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in JavaScript

Design Add and Search Words Data Structure

Explore how to design a WordDictionary class implementing add and search functionalities for words, including support for wildcard dot characters. Understand using the trie data structure for efficient string storage and prefix matching. This lesson helps you grasp the problem constraints and implement your solution in JavaScript within a hands-on coding environment.

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, 10210^2 calls will be made to Add Word() , Get Words() and Search Word().

Examples

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

1 / 4

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5

Try it yourself

Implement your solution in word_dictionary.js in the following coding playground.

JavaScript
usercode > word_dictionary.js
import TrieNode from "./trie_node.js";
// Tip: You may use some of the code templates provided
// in the support files
class WordDictionary {
    constructor() {
        // Initialize your variables here
    }
    addWord(word) {
        // write your code here
    }
    searchWord(word) {
        // Replace this placeholder retrun statement with your code
        return false;
    }
    getWords() {
        // write your code here   
    }
}
export default WordDictionary;
Design Add and Search Words Data Structure