题目描述

实现一个带有buildDict, 以及search方法的魔法字典。

对于buildDict方法，你将被给定一串不重复的单词来构建一个字典。

对于search方法，你将被给定一个单词，并且判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

样例

Input: buildDict([“hello”, “leetcode”]), Output: Null
Input: search(“hello”), Output: False
Input: search(“hhllo”), Output: True
Input: search(“hell”), Output: False
Input: search(“leetcoded”), Output: False

算法 字典树

C++ 代码

class MagicDictionary {
public:

    int trie[10001][26];
    int isword[10001];
    int idx;

    MagicDictionary() {
        idx = 0;
        memset(trie,0,sizeof trie);
        memset(isword,0,sizeof isword);
    }

    void insert(string s){
        int p = 0;
        for (int i = 0; i < s.size(); ++i){
            if(trie[p][s[i] - 'a'] == 0) trie[p][s[i] - 'a'] = ++idx;
            p = trie[p][s[i] - 'a'];
        }
        isword[p] = 1;
    }

    void buildDict(vector<string> dict) {
        for (auto &s:dict)
            insert(s);
    }

    bool dfs(int p,int u,string word,bool error){
        if (error > 1)  return false;
        if (u == word.size()){
            return isword[p] && error;   
        }
        bool flag;
        for (int i = 0; i < 26; ++i){
            if (trie[p][i] != 0){
                if (i == word[u] - 'a'){
                    if(dfs(trie[p][i],u + 1,word,error))
                        return true;
                }
                else if (error == false && dfs(trie[p][i],u + 1,word,true)){
                    return true;
                }
            }
        }
        return false;
    }

    bool search(string word) {
       return dfs(0,0,word,false);
    }
};