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

Solution: Design Add and Search Words Data Structure

Explore how to design and implement a WordDictionary data structure that supports adding words, searching with wildcard characters, and retrieving all stored words. Understand the use of trie for efficient string storage and lookup, and analyze time and space complexities of these operations.

We'll cover the following...

Statement

Design a data structure that enables the addition of new words, facilitates word search, and provides the count of all words.

Implement a struct, WordDictionary, which should provide the following functionalities:

  • NewWordDictionary(): 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 struct.

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 ...