Design Add and Search Words Data Structure

Design Add and Search Words Data Structure - Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Note: The dot character '.' acts as a wildcard that can match any single letter.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"], inputs = [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

› Output: [null,null,null,null,false,true,true,true]

💡 Note: Create dictionary, add 'bad', 'dad', 'mad'. Search 'pad' (false), 'bad' (true), '.ad' matches bad/dad/mad (true), 'b..' matches bad (true)

Example 2 — Wildcard Patterns

$ Input: operations = ["WordDictionary","addWord","search","search","search"], inputs = [[],["a"],["."],[".."],["."]]

› Output: [null,null,true,false,true]

💡 Note: Add single letter 'a'. Search '.' matches 'a' (true), '..' is length 2 but 'a' is length 1 (false), '.' matches 'a' (true)

Example 3 — Multiple Wildcards

$ Input: operations = ["WordDictionary","addWord","addWord","search","search"], inputs = [[],["word"],["world"],["...d"],["....d"]]

› Output: [null,null,null,false,true]

💡 Note: Add 'word' and 'world'. Search '...d' is length 4 but no 4-letter words end in 'd' (false), '....d' matches 'world' (true)

Constraints

1 ≤ word.length ≤ 25
word consists of lowercase English letters
At most 3 × 10⁴ calls to addWord and search

Visualization

Tap to expand

Understanding the Visualization

Add Words

Store words: 'bad', 'dad', 'mad'

Search Pattern

Query with wildcard: '.ad'

Match Result

Return true (pattern matches stored words)

Key Takeaway

🎯 Key Insight: Trie structure with DFS traversal efficiently handles wildcard search by exploring all possible paths when encountering '.' characters

Asked in

f Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is using a Trie data structure for efficient prefix storage combined with DFS traversal to handle wildcard characters. The optimal approach builds a Trie tree and uses depth-first search when encountering '.' to explore all possible character matches. Time: O(m×26^k) for search, Space: O(ALPHABET_SIZE×N×M) for storage.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with List Storage	O(n×m)	O(n×m)	Store words in a list and search through all words for each query
Length-Based Grouping	O(k×m)	O(n×m)	Group words by length to reduce search space for pattern matching
Trie with DFS (Optimal)	O(m×26^k)	O(ALPHABET_SIZE×N×M)	Use Trie data structure with DFS traversal for efficient wildcard pattern matching

Brute Force with List Storage — Algorithm Steps

Store words in a list
For search, iterate through all stored words
Check each word character by character, treating '.' as wildcard

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Words

Add words to a simple list

Search Pattern

Check each word against search pattern

Match Found

Return true if any word matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 10000
#define MAX_WORD_LEN 100

typedef struct {
    char words[MAX_WORDS][MAX_WORD_LEN];
    int count;
} WordDictionary;

WordDictionary* wordDictionaryCreate() {
    WordDictionary* wd = (WordDictionary*)malloc(sizeof(WordDictionary));
    wd->count = 0;
    return wd;
}

void wordDictionaryAddWord(WordDictionary* wd, char* word) {
    strcpy(wd->words[wd->count], word);
    wd->count++;
}

bool wordDictionarySearch(WordDictionary* wd, char* word) {
    int wordLen = strlen(word);
    for (int i = 0; i < wd->count; i++) {
        if (strlen(wd->words[i]) == wordLen) {
            bool match = true;
            for (int j = 0; j < wordLen; j++) {
                if (word[j] != '.' && word[j] != wd->words[i][j]) {
                    match = false;
                    break;
                }
            }
            if (match) return true;
        }
    }
    return false;
}

char* solution(char** operations, char*** inputs, int opCount) {
    WordDictionary* wd = wordDictionaryCreate();
    char* result = (char*)malloc(1000);
    strcpy(result, "[");
    
    for (int i = 0; i < opCount; i++) {
        if (i > 0) strcat(result, ",");
        
        if (strcmp(operations[i], "WordDictionary") == 0) {
            strcat(result, "null");
        } else if (strcmp(operations[i], "addWord") == 0) {
            wordDictionaryAddWord(wd, inputs[i][0]);
            strcat(result, "null");
        } else if (strcmp(operations[i], "search") == 0) {
            bool found = wordDictionarySearch(wd, inputs[i][0]);
            strcat(result, found ? "true" : "false");
        }
    }
    strcat(result, "]");
    return result;
}

int main() {
    char* result = solution(NULL, NULL, 0);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Search checks all n words, each comparison takes O(m) where m is word length

✓ Linear Growth

Space Complexity

O(n×m)

Store all n words of average length m in the list

⚡ Linearithmic Space

78.0K Views

High Frequency

~25 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with List Storage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler