Implement Magic Dictionary - Practice Coding Problems

Implement Magic Dictionary - Problem

Design a data structure that is initialized with a list of different words. Given a string, determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

MagicDictionary() - Initializes the object
buildDict(String[] dictionary) - Sets the data structure with an array of distinct strings dictionary
search(String searchWord) - Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MagicDictionary", "buildDict", "search", "search"], inputs = [[], ["hello", "leetcode"], "hello", "hhllo"]

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

💡 Note: Initialize dictionary with ["hello", "leetcode"]. Search "hello" returns false (can't change to itself). Search "hhllo" returns true (change 'h' to 'e' makes "hello")

Example 2 — Multiple Words

$ Input: operations = ["MagicDictionary", "buildDict", "search", "search"], inputs = [[], ["hello", "hallo"], "hello", "hillo"]

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

💡 Note: Dictionary has ["hello", "hallo"]. Search "hello" returns true (change 'e' to 'a' makes "hallo"). Search "hillo" returns true (change 'i' to 'e' makes "hello")

Example 3 — No Match

$ Input: operations = ["MagicDictionary", "buildDict", "search"], inputs = [[], ["hello"], "hellllo"]

› Output: [null, null, false]

💡 Note: Dictionary has ["hello"]. Search "hellllo" returns false (different lengths, cannot match with exactly one change)

Constraints

1 ≤ dictionary.length ≤ 100
1 ≤ dictionary[i].length ≤ 100
dictionary[i] consists of only lower-case English letters
All the strings in dictionary are distinct
1 ≤ searchWord.length ≤ 100
searchWord consists of only lower-case English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Dictionary: ["hello", "leetcode"], Search: "hhllo"

Process

Check if exactly 1 character change creates a match

Output

Return true (hhllo → hello with 1 change)

Key Takeaway

🎯 Key Insight: Pre-processing dictionary words into patterns enables O(1) lookup per search pattern

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to either compare each search word with all dictionary words character by character, or pre-process dictionary words into patterns for faster lookup. The hash map approach is optimal for multiple searches: Time O(n×m² + k×m), Space O(n×m²).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Patterns	O(n × m² + k × m)	O(n × m²)	Pre-process dictionary words into patterns for faster lookup
Brute Force Comparison	O(n × m × k)	O(n × m)	For each search, compare with every dictionary word character by character

Hash Map with Patterns — Algorithm Steps

Build patterns: 'hello' → {'*ello', 'h*llo', 'he*lo', etc.}
Store patterns in hash map with original words
For search word, generate all patterns
Check if any pattern exists in map

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Patterns

Create patterns like 'h*llo', 'he*lo' for each word

Store in Map

Map patterns to original words

Generate search patterns and check map

Code -

solution.c — C

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

#define MAX_PATTERNS 10000
#define MAX_WORDS_PER_PATTERN 100

typedef struct {
    char patterns[MAX_PATTERNS][20];
    char words[MAX_PATTERNS][MAX_WORDS_PER_PATTERN][20];
    int wordCounts[MAX_PATTERNS];
    int patternCount;
} MagicDictionary;

MagicDictionary* magicDictionaryCreate() {
    MagicDictionary* obj = (MagicDictionary*)malloc(sizeof(MagicDictionary));
    obj->patternCount = 0;
    return obj;
}

int findPattern(MagicDictionary* obj, char* pattern) {
    for (int i = 0; i < obj->patternCount; i++) {
        if (strcmp(obj->patterns[i], pattern) == 0) {
            return i;
        }
    }
    return -1;
}

void magicDictionaryBuildDict(MagicDictionary* obj, char** dictionary, int dictionarySize) {
    obj->patternCount = 0;
    for (int i = 0; i < dictionarySize; i++) {
        char* word = dictionary[i];
        int len = strlen(word);
        for (int j = 0; j < len; j++) {
            char pattern[20];
            strcpy(pattern, word);
            pattern[j] = '*';
            
            int idx = findPattern(obj, pattern);
            if (idx == -1) {
                strcpy(obj->patterns[obj->patternCount], pattern);
                obj->wordCounts[obj->patternCount] = 0;
                idx = obj->patternCount++;
            }
            strcpy(obj->words[idx][obj->wordCounts[idx]], word);
            obj->wordCounts[idx]++;
        }
    }
}

bool magicDictionarySearch(MagicDictionary* obj, char* searchWord) {
    int len = strlen(searchWord);
    for (int i = 0; i < len; i++) {
        char pattern[20];
        strcpy(pattern, searchWord);
        pattern[i] = '*';
        
        int idx = findPattern(obj, pattern);
        if (idx != -1) {
            for (int j = 0; j < obj->wordCounts[idx]; j++) {
                if (strcmp(obj->words[idx][j], searchWord) != 0) {
                    return true;
                }
            }
        }
    }
    return false;
}

char* solution(char** operations, int operationsSize, char*** inputs) {
    MagicDictionary* magicDict = magicDictionaryCreate();
    char* result = (char*)malloc(1000);
    strcpy(result, "[");
    
    for (int i = 0; i < operationsSize; i++) {
        if (i > 0) strcat(result, ",");
        
        if (strcmp(operations[i], "MagicDictionary") == 0) {
            strcat(result, "null");
        } else if (strcmp(operations[i], "buildDict") == 0) {
            strcat(result, "null");
        } else if (strcmp(operations[i], "search") == 0) {
            bool searchResult = magicDictionarySearch(magicDict, inputs[i][0]);
            strcat(result, searchResult ? "true" : "false");
        }
    }
    strcat(result, "]");
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n × m² + k × m)

Build: n words × m² patterns per word, Search: k operations × m patterns

✓ Linear Growth

Space Complexity

O(n × m²)

Store up to n×m² patterns in hash map

⚡ Linearithmic Space

67.0K Views

Medium Frequency

~25 min Avg. Time

892 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

Hash Map with Patterns — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler