[C language brush leetcode] 676 Implement a magic Dictionary (m)

【

Design a data structure initialized with word list , Words in the word list Different from each other . If you give a word , Please decide whether you can replace only one letter of this word with another , Make the formed new words exist in the dictionary you build .

Realization MagicDictionary class ：

MagicDictionary() Initialize object
void buildDict(String[] dictionary) Use string arrays  dictionary Set the data structure ,dictionary Strings in are different from each other
bool search(String searchWord) Given a string searchWord , Determine whether you can only put... In the string One Replace one letter with another , So that the new string formed can match any string in the dictionary . If possible , return true ; otherwise , return false .
 

Example ：

Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
Output
[null, null, false, true, false, false]

explain
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // return False
magicDictionary.search("hhllo"); // Put the second 'h' Replace with 'e' Can match "hello" , So back True
magicDictionary.search("hell"); // return False
magicDictionary.search("leetcoded"); // return False
 

Tips ：

1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] It's only made up of lowercase letters
dictionary All the strings in Different from each other
1 <= searchWord.length <= 100
searchWord It's only made up of lowercase letters
buildDict Only in search Before calling once
Call at most 100 Time search

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/implement-magic-dictionary
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

】

At first, I thought it was complicated , I thought I was going to use UTHASH, But the title says buildDict  Only in  search  Before calling once , Then the dictionary is fixed , No, I need to add , This greatly simplifies the subject . So when defining a structure , Direct a two-dimensional array to the word array .

When a word changes several digits, it becomes another word , That is, two words are only a few digits worse than each other .

typedef struct {
    char **words;
    int size;
} MagicDictionary;


MagicDictionary* magicDictionaryCreate() {
    MagicDictionary *obj = (MagicDictionary *)malloc(sizeof(MagicDictionary));

    return obj;
}

void magicDictionaryBuildDict(MagicDictionary* obj, char ** dictionary, int dictionarySize) {
    obj->words = dictionary;
    obj->size = dictionarySize;
}

bool magicDictionarySearch(MagicDictionary* obj, char * searchWord) {
    int len = strlen(searchWord);
    int i, j;

    //  Traverse every character in the dictionary 
    for (i = 0; i < obj->size; i++) {
        int objlen = strlen(obj->words[i]);
        if (objlen != len) {
            continue; //  If the length is inconsistent , There is no need to compare 
        }

        int diff = 0;
        for (j = 0; j < len; j++) {
            if (obj->words[i][j] != searchWord[j]) { //  Compare each word 
                diff++;
            }

            if (diff > 1) {
                break; //  If the number of digits of a word is more than two, it is inconsistent , Start comparing the next word 
            }
        }

        if (diff == 1) { //  Come here diff=1 It means that you can return if you meet the meaning of the question true 了 
            return true;
        }

    }

    return false; //  It is definitely not satisfying to come here , Otherwise, the front will return 
}

void magicDictionaryFree(MagicDictionary* obj) {
    free(obj);
}
/*
 Be careful ：
1. ‘ Can you just replace one letter with another in this word , Make the formed new words exist in the dictionary you build ’
 namely   There is only one character difference between two words .
2. buildDict  Build only once , Then it won't change . This hidden condition can simplify the problem 
3.  Structure defines a two-dimensional pointer , Direct to dictionary That's it 

*/