【leetcode】【剑指offer Ⅱ】064. 神奇的字典

问题描述：

• 实现 MagicDictionary 类：
  • MagicDictionary() 初始化对象。
  • void buildDict(vector dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同。
  • bool search(string searchWord) 给定一个字符串 searchWord，判定能否只将字符串中一个字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配，如果可以，返回 true，否则返回 false。

核心思路：

• 该题可以用哈希表来解题，在存入哈希表的时候单独将字符串每一个字符置为 # 存入，同理搜索的时候也可以将字符串每一个字符置为 #。
• 更好的方法仍然是前缀树解法。
  • void buildDict(vector dictionary) 函数将 dictionary 中的所有单词存入前缀树中。
  • bool search(string searchWord) 函数则在前缀树中递归搜索 searchWord，过程中维护一个布尔变量 flag，该 flag 标示是否修改过某个字符，flag = true 表示之前已经修改过一次字符。【如果在本次递归访问的过程中 flag = false，则说明此前没有修改过字符，在当前访问中访问所有子节点并讲 flag 置为 true 传递下去即可】

代码实现：

class Trie
{
public:
    vector<Trie*> next;
    bool isEnd;
public:
    /** Initialize your data structure here. */
    Trie(): next(26), isEnd(false) {}
    
    /** Inserts a word into the trie. */
    void insert(string word)
    {
        Trie* cur = this;
        for(char& c : word)
        {
            if(!cur->next[c - 'a']) cur->next[c - 'a'] = new Trie();
            cur = cur->next[c - 'a'];
        }
        cur->isEnd = true;
    }
};

class MagicDictionary
{
private:
    Trie* root;
    bool dfs(string& str,Trie* cur, int i, bool flag)
    {
        if(!cur) return false;
        if(i == str.size()) return (flag and cur->isEnd); // 在字符串结尾，需要判断是否已经修改过一次，同时需要判断 isEnd 标志
        bool ans = false;
        int c = str[i]; c -= 'a';
        ans |= dfs(str, cur->next[c], i+1, flag); // 按照原字符串的字符来进行访问
        if(ans) return ans;
        if(flag) return false; // 如果 flag 为 false，则说明此前已经修改过一次字符，后续不再进行修改
        // 后续修改一次字符
        for(int j = 0; j < 26; ++j) if(c != j)
        {
            ans |= dfs(str, cur->next[j], i+1, true);
            if(ans) return ans;
        }
        return ans;
    }
public:
    /** Initialize your data structure here. */
    MagicDictionary()
    {
        root = new Trie();
    }
    
    void buildDict(vector<string> dictionary)
    {
        for(auto& dict : dictionary)
            root->insert(dict);
    }
    
    bool search(string searchWord)
    {
        return dfs(searchWord, root, 0, false);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61