题目描述

题意：实现一个带有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

Note:

1. You may assume that all the inputs are consist of lowercase letters a-z.

算法1

(Trie + DFS)

题解：这题需要注意的是必须要替换一个字符才返回true，如果单词在字典中已经有了则要返回false。首先我们考虑使用Trie树来存储所有的单词。在建立好Trie树后，对于每一个单词我们需要进行从第一个字符进行比较分为两种情况：

• 如果当前字符和之前的字符相同，我们可以继续往下搜索，另一方面，如果我们之前没有替换过单词，我们现在可以考虑替换这个字符，再继续往下搜索。
• 如果当前字符和之前的字符不相同，我们则必须替换这个字符。如果之前已经替换过了说明当前匹配不合法，直接返回false。
• 最后如果搜索完整个单词并且恰好替换了一次并且当前节点是单词节点，我们返回true。

上述搜索可以使用DFS来解决，我们使用cnt来标记已经替换过几个字符了。

时间复杂度分析：建立Trie树过程$O(n*L)$。

最坏情况下，对于每个单词我们都要遍历整棵Trie树，所以总的时间复杂度为$O(n\*L\*size)$

C++ 代码

class MagicDictionary {
public:
    struct node{
        bool iskey;
        node* next[26];
        node(){
            iskey = false;
            for(int i = 0 ; i < 26 ; i ++)
                next[i] = nullptr;
        }
    };
    node* root;
    /** Initialize your data structure here. */
    MagicDictionary() {
        root = new node();
    }

    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for(auto word:dict)
        {
            node* p = root;
            for(auto c:word)
            {
                int u = c -'a';
                if(!p->next[u]) p->next[u] = new node();
                p = p->next[u];
            }
            p->iskey =true;
        }
    }

    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {   
        return dfs(root,0,word.length(),word,0);
    }
    bool dfs(node* p,int i,int n,string &word,int cnt)
    {
        if(i == n) return p->iskey && cnt == 1;
        int u = word[i] - 'a';
        if(p->next[u])
        {
            if(dfs(p->next[u],i + 1,n,word,cnt))
                return true;
            if(cnt == 0)
            {
                for(int k = 0 ; k < 26 ; k ++)
                {
                    if(k != u && p->next[k] && dfs(p->next[k],i + 1,n,word,cnt + 1))
                        return true;
                }
            }
        }
        else
        {
            if(cnt == 1) return false;
            for(int k = 0 ; k < 26 ; k ++)
            {
                if(p->next[k] && dfs(p->next[k],i + 1,n,word,cnt + 1))
                        return true;
            }
        }
        return false;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dict);
 * bool param_2 = obj->search(word);
 */