Problem Breakdown
We need to implement a data structure that stores a collection of words and supports queries where we check if the query string can become an existing word by changing exactly one character.
Inputs:
dictionary: An array of distinct strings (lowercase English letters).searchWord: A single string for querying.
Outputs:
- Boolean: True if a valid transformation exists, False otherwise.
Implicit Constraints & Edge Cases:
- Exact Match: If the search word already matches a dictionary word exactly, that counts as zero changes. The requirement is exactly one change, so exact matches return
False. - Length Mismatch: A search word cannot match any dictionary word if their lengths differ (changing characters doesn’t add or remove them). We must check length equality before comparing content to avoid index errors and wasted computation.
- Multiple Differences: If the Hamming distance exceeds one, we can stop counting early for that specific pair of words.
- Constraints Analysis: The dictionary size is small () and word length is short (). This suggests a linear scan through the stored dictionary during each search call is acceptable, though we should still write efficient logic to handle larger inputs if constraints were relaxed.
Intuition
The core task is checking for an “edit distance of exactly one” between searchWord and any word in our collection.
Brute Force Approach: For every query, iterate through the entire dictionary list. For each candidate word:
- Check length equality (pruning).
- Count character mismatches.
- If count == 1, return True immediately.
If we finish checking all words without finding a match with exactly one difference, return False.
Why Brute Force is Insufficient for Large Scale:
While the constraints here () allow per search easily (roughly 10,000 operations max), in production systems where dictionary could be large or queries frequent, we would want to avoid scanning every word. A Trie structure allows us to traverse character by character and prune branches that don’t match the prefix of the query + one substitution. However, given these specific constraints, a simple list iteration is often preferred for code simplicity unless performance profiling dictates otherwise. I will implement the linear scan approach as it balances readability with sufficient efficiency here.
Approach
- Initialization: Create an empty list to store dictionary words in
__init__. - Build Dictionary (
buildDict): Populate the internal storage list with the provided array of strings. Since constraints guarantee distinct strings, we don’t need deduplication logic here. - Search Logic (
search):- Iterate through each word
targetin our stored dictionary. - Check if
len(searchWord) == len(target). If not, skip (length mismatch). - Initialize a counter for differences to zero.
- Loop index from 0 to length-1 comparing characters at the same position. Increment difference count on mismatch.
- Optimization: Break early if difference count exceeds 1.
- After loop, check if
difference_count == 1. If so, return True immediately (short-circuit).
- Iterate through each word
- Finalization: If the loop completes without returning True, return False.
Complexity Analysis
- Time Complexity:
- Build: where N is dictionary size and L is average word length.
- Search per call: in worst case (K search calls), but practically bounded by early exits on mismatch or count > 1. With given constraints, this effectively behaves like constant time relative to typical input sizes for LeetCode limits ().
- Overall: . Given the small fixed bounds in problem description, space and time are negligible.
- Space Complexity:
- to store the dictionary words.
Solution
class MagicDictionary:
def __init__(self):
self.dictionary = []
def buildDict(self, dictionary: List[str]) -> None:
"""Stores the distinct strings provided in the array."""
# Constraints guarantee distinct strings and lowercase letters only.
self.dictionary.extend(dictionary)
def search(self, searchWord: str) -> bool:
"""Checks if changing exactly one character matches a word in dictionary."""
for target_word in self.dictionary:
# Optimization 1: Length mismatch means they can't match via substitution
if len(searchWord) != len(target_word):
continue
diff_count = 0
length = len(searchWord)
# Count character differences between searchWord and current dictionary word
for i in range(length):
if searchWord[i] != target_word[i]:
diff_count += 1
# Optimization 2: If more than one difference, this pair is invalid.
# We can stop counting early to save cycles.
if diff_count > 1:
break
# Check if we found exactly one mismatch for a valid length match
if diff_count == 1:
return True
return False
# Example usage matching the problem description logic (not part of class)
# magicDictionary = MagicDictionary()
# magicDictionary.buildDict(["hello", "leetcode"])
# print(magicDictionary.search("hhllo")) # Output: True
Edge Cases Handled
- Exact Match: The code counts differences. An exact match results in
diff_count == 0. Since we check specifically for== 1, this correctly returns False (as per problem requirement of exactly one change). - Length Mismatch: Checked via
if len(searchWord) != len(target_word): continuebefore character comparison to prevent index errors and unnecessary work. - Early Termination: The inner loop breaks if
diff_count > 1, preventing full iteration of long strings when a match is impossible, improving average-case performance. - Empty Search/Dict: Constraints state lengths , but the logic holds (loop won’t run or returns False) without crashing.