grid47 Exploring patterns and algorithms
Aug 31, 2024
6 min read
Solution to LeetCode 676: Implement Magic Dictionary Problem
Design a data structure that supports searching for words that can be matched by changing exactly one character.
Problem
Approach
Steps
Complexity
Input: You will be given a list of distinct words to initialize the MagicDictionary, and you need to search for words that can match by changing exactly one character.
Example: ["abc", "abd", "bbc"]
Constraints:
• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• All words in the dictionary are distinct.
• 1 <= searchWord.length <= 100
Output: Return true if you can change exactly one character in the searchWord to match any word in the dictionary. Otherwise, return false.
Example: true
Constraints:
• The output will always be a boolean value.
Goal: The goal is to determine whether exactly one character in the search word can be changed to match any word from the dictionary.
Steps:
• 1. Store the words from the dictionary in a way that makes checking for a possible one-character change efficient.
• 2. For each character position in the search word, check if changing that character makes the word match any dictionary word.
Goal: The constraints of this problem ensure that dictionary and search words are not too large, allowing efficient checks.
Steps:
• All words in the dictionary and the search word consist only of lowercase English letters.
• The dictionary contains no duplicate words.
Assumptions:
• The dictionary will be built only once, and search operations will be performed after the dictionary is built.
• Input: ["hello", "leetcode"]
• Explanation: In this case, searching for the word 'hhllo' should return true, as changing the second 'h' to 'e' matches the word 'hello'.
• Input: ["abc", "abd", "bbc"]
• Explanation: Here, searching for 'abc' should return true since it matches with the dictionary word 'abd' by changing the second 'c' to 'd'.
Approach: We will create a dictionary where we store each word with possible one-character changes for efficient searching.
Observations:
• We need to consider all possible words that can be made by changing one character in the search word.
• The efficient way to store and check possible matches is to store substrings of each word where one character has been removed, then use this for searching.
Steps:
• 1. Create a dictionary that stores each word's possible substrings where one character has been removed.
• 2. For each search word, check if changing exactly one character makes it match any word in the dictionary.
Empty Inputs:
• This problem doesn't deal with empty dictionaries or search words as they are constrained to have at least one character.
Large Inputs:
• Ensure the dictionary and search word sizes can be handled efficiently, even with the maximum constraints.
Special Values:
• If the dictionary contains identical words or the search word is already in the dictionary, it should return false.
Constraints:
• Efficient storage of dictionary words is key to handling the maximum input size within time limits.
public:MagicDictionary() {
}
voidbuildDict(vector<string> dict) {
for(string s: dict) {
int n = s.length();
for(int i =0; i < n; i++) {
string t = s.substr(0, i) + s.substr(i+1);
pair<int, char> p(i, s[i]);
mp[t].push_back(p);
}
}
}
boolsearch(string word) {
for(int i =0; i < word.size(); i++) {
string key = word.substr(0, i) + word.substr(i+1);
for(pair<int, char>sk : mp[key])
if(sk.first == i && sk.second!=word[i])
returntrue;
}
returnfalse;
}
};
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary* obj = new MagicDictionary();
* obj->buildDict(dictionary);
* bool param_2 = obj->search(searchWord);
1 : Class Definition
public:
This marks the start of the public section of the class definition, indicating the access specifier for the methods and variables that follow.
2 : Constructor
MagicDictionary() {
This is the constructor of the `MagicDictionary` class. It initializes the object, though in this case, there is no explicit initialization logic.
3 : Function Definition
voidbuildDict(vector<string> dict) {
This defines the `buildDict` function, which takes a vector of strings (`dict`) and processes each word to store its modified versions.
4 : For Each Word
for(string s: dict) {
This loop iterates through each word in the dictionary (`dict`).
5 : Length of Word
int n = s.length();
Here, we store the length of the current word `s` in the variable `n`.
6 : Loop Through Word Characters
for(int i =0; i < n; i++) {
This inner loop iterates over each character of the word `s`, allowing us to create modified versions of the word by removing one character at a time.
7 : Create Modified Word
string t = s.substr(0, i) + s.substr(i+1);
This creates a modified version of the word `s` by removing the character at index `i`. The modified word is stored in `t`.
8 : Create Pair
pair<int, char> p(i, s[i]);
We create a pair `p` consisting of the index `i` and the character `s[i]` that was removed in the modified word.
9 : Store in Map
mp[t].push_back(p);
The modified word `t` is used as the key, and the pair `p` is pushed into the corresponding vector in the map `mp`. This helps track the modified versions of each word.
10 : Function Definition
boolsearch(string word) {
This defines the `search` function, which takes a word as input and checks if it can be formed by modifying exactly one character of an existing word in the dictionary.
11 : Loop Through Word Characters
for(int i =0; i < word.size(); i++) {
This loop iterates through each character of the input word `word`.
