Build a Fuzzy Keyword Index

Problem Statement

You are tasked with building a search service that allows users to perform "fuzzy" lookups on a fixed dictionary of $N$ words. A query is considered a match if a word exists in the dictionary with an edit distance (Levenshtein distance) of at most $K=1$ from the query string.

Implement a class FuzzyIndex that optimizes for repeated query performance.

Requirements

• __init__(dictionary): Preprocesses the list of unique words to enable fast lookups.
• search(query): Returns a list of all words in the dictionary that have an edit distance of 0 or 1 from the query.

Constraints

• Number of words $N$ is up to 50,000.
• Maximum length of any word $L$ is 20.
• Preprocessing time should be reasonable (e.g., under 5 seconds).
• search should be significantly faster than iterating through all words.

Example

dictionary = ["apple", "apply", "banana", "pear"]
index = FuzzyIndex(dictionary)
index.search("appel")  # Returns ['apple']
index.search("apple")  # Returns ['apple', 'apply']
index.search("banan")  # Returns ['banana']

Edge Cases

• Empty dictionary or empty query strings.
• Queries that are much longer or shorter than any word in the dictionary.
• Queries resulting in multiple matches (e.g., distance 1 for multiple dictionary words).