小鲸鱼的梦境
0%

『LeetCode』676 实现一个魔法字典

发表于 分类于 Valine：
本文字数： 7.7k 阅读时长 ≈ 7 分钟

题目

676. 实现一个魔法字典

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

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

示例：

输入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

提示：

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100 次 search

标签

设计, 字典树, 哈希表, 字符串

相似题目

题解

【实现一个魔法字典】一题三解『枚举&模拟&字典树』

枚举&模拟

使用哈希表存下字典，再对单词逐个字母进行替换成其他 25 个字母后检查是否在哈希表中。

效率较低，但在本题的数据范围内可以通过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Code language: Python
class MagicDictionary:

    def __init__(self):
        self.alp = "qwertyuioplkjhgfdsazxcvbnm"
        self.d = set()

    def buildDict(self, dictionary: List[str]) -> None:
        self.d = set(dictionary)

    def search(self, searchWord: str) -> bool:
        word = list(searchWord)
        for i, j in enumerate(word):
            for s in self.alp:
                if s != j:
                    word[i] = s
                    if "".join(word) in self.d:
                        return True
            word[i] = j
        return 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
// Code language: Java
class MagicDictionary {
    Set<String> st;
    public MagicDictionary() {

    }
    
    public void buildDict(String[] dictionary) {
        st = new HashSet<>();
        for (String w: dictionary) st.add(w);
    }
    
    public boolean search(String searchWord) {
        char[] word = searchWord.toCharArray();
        for (int i = 0, n = word.length; i < n; ++i) {
            char c = word[i];
            for (int j = 0; j < 26; ++j) {
                word[i] = (char)('a' + j);
                if (c != word[i] && st.contains(String.copyValueOf(word))) return true;
            }
            word[i] = c;
        }
        return 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
// Code language: C++
class MagicDictionary {
public:
    unordered_set<string> st;
    MagicDictionary() {

    }
    
    void buildDict(vector<string> dictionary) {
        for (string& word: dictionary) st.emplace(word);
    }
    
    bool search(string searchWord) {
        for (int i = 0, n = searchWord.size(); i < n; ++i) {
            char c = searchWord[i];
            for (int j = 0; j < 26; ++j) {
                searchWord[i] = (char)('a' + j);
                if (c != searchWord[i] && st.find(searchWord) != st.end()) return true;
            }
            searchWord[i] = c;
        }
        return false;
    }
};
  • 时间复杂度: 建立哈希表 \(O(n)\), \(n\) 是字典的大小, \(O(Cm^2)\), \(m\) 是调用 search 时单词的长度, \(C\) 是固定的常数 \(26\), \(m^2\) 是因为计算字符串的哈希值需要 \(O(m)\).
  • 空间复杂度: \(O(n)\)

模拟&搜索

将搜索单词与字典中的单词逐字母进行对比，检查字典中是否存在“与搜索单词有且仅有一个字符不同”

与上一个方法相比常数减小了，效率大幅度提高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MagicDictionary:

    def __init__(self):
        self.d = list()

    def buildDict(self, dictionary: List[str]) -> None:
        self.d = dictionary

    def check(self, word1, word2):
        """ 检查 word1 与 word2 是否只有一个字符不同 """
        if len(word1) != len(word2):
            return False
        cnt = 0
        for a, b in zip(word1, word2):
            if a != b:
                cnt += 1
                if cnt > 1:
                    return False
        return cnt == 1

    def search(self, searchWord: str) -> bool:
        return any(self.check(searchWord, w) for w in self.d)
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
// Code language: Java
class MagicDictionary {
    String[] dict;
    public MagicDictionary() {

    }
    
    public void buildDict(String[] dictionary) {
        dict = dictionary;
    }
    
    public boolean check(String word1, String word2) {
        // 检查 word1 与 word2 是否只有一个字符不同
        int n = word1.length();
        if (n != word2.length()) return false;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (word1.charAt(i) != word2.charAt(i)) {
                if (++cnt > 1) return false;
            }
        }
        return cnt == 1;
    }
    
    public boolean search(String searchWord) {
        for (String word: dict) {
            if (check(searchWord, word)) return true;
        }
        return 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
// Code language: C++
class MagicDictionary {
public:
    vector<string> dict;
    MagicDictionary() {

    }
    
    void buildDict(vector<string> dictionary) {
        dict = dictionary;
    }

    bool check(string& word1, string& word2) {
        if (word1.size() != word2.size()) return false;
        int cnt = 0;
        for (int i = 0, n = word1.size(); i < n; ++i) {
            if (word1[i] != word2[i] && ++cnt > 1) return false; 
        }
        return cnt == 1;
    }
    
    bool search(string searchWord) {
        for (string& word: dict) {
            if (check(searchWord, word)) return true;
        }
        return false;
    }
};
  • 时间复杂度: \(O(nm)\), \(n\) 是字典的大小, \(m\) 是调用 search 时单词的长度
  • 空间复杂度: \(O(1)\), 忽略题目所给字典的空间

字典树搜索

对方法二进行改进，使用字典树加速搜索，字典树相关的内容可以看 LeetCode 的另外一题：实现 Trie (前缀树) (中等)

由于原字符有且仅有一个字符与所给字典不同，这里可以使用深度优先对字典树进行搜索。

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
# Code language: Python
class TrieNode:
    def __init__(self):
        self.end = False
        self.next = defaultdict(TrieNode)

class Trie:
    def __init__(self, dictionary):
        self.root = TrieNode()
        for s in dictionary:
            self.add(s)
    
    def add(self, s):
        cur = self.root
        for c in s:
            cur = cur.next[c]
        cur.end = True
    
    def dfs(self, word, idx, root, cnt):
        """ 对字典树进行深度优先搜索 """
        if idx == len(word):
            return cnt == 0 and root.end
        for i, j in root.next.items():
            if word[idx] == i:
                if self.dfs(word, idx + 1, j, cnt):
                    return True
            elif cnt > 0 and self.dfs(word, idx + 1, j, cnt - 1):
                return True
        return False

class MagicDictionary:

    def __init__(self):
        pass

    def buildDict(self, dictionary: List[str]) -> None:
        self.tree = Trie(dictionary)

    def search(self, searchWord: str) -> bool:
        return self.tree.dfs(searchWord, 0, self.tree.root, 1)
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
// Code language: Java
class MagicDictionary {
    // 使用二维数组代替动态字典树
    static int[][] tree = new int[30000][26];
    static boolean[] end = new boolean[30000];
    int top = 1;

    public MagicDictionary() {
        Arrays.fill(end, false);
        Arrays.fill(tree[0], -1);
    }

    public void add(String word) {
        // 在字典树中插入单词
        int root = 0;
        for (int i = 0, n = word.length(); i < n; ++i) {
            int idx = word.charAt(i) - 'a';
            if (tree[root][idx] == -1) {
                Arrays.fill(tree[top], -1);
                tree[root][idx] = top++;
            }
            root = tree[root][idx];
        }
        end[root] = true;
    }
    
    public void buildDict(String[] dictionary) {
        for (String word: dictionary) add(word);
    }

    public boolean dfs(String word, int idx, int root, int cnt) {
        if (idx == word.length()) return cnt == 0 && end[root];
        for (int i = 0; i < 26; ++i) {
            if (tree[root][i] == -1) continue;
            if (i == word.charAt(idx) - 'a') {
                if (dfs(word, idx + 1, tree[root][i], cnt)) return true;
            }
            else if (cnt > 0 && dfs(word, idx + 1, tree[root][i], cnt - 1)) return true;
        }
        return false;
    }
    
    public boolean search(String searchWord) {
        return dfs(searchWord, 0, 0, 1);
    }
}
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
// Code language: C++
class TrieNode {
public:
    vector<TrieNode*> nxt = vector<TrieNode*>(26, nullptr);
    bool end = false;
};

class MagicDictionary {
public:
    TrieNode* root = new TrieNode();
    MagicDictionary() {
    }

    void add(string& word) {
        TrieNode* p = root;
        for (char c: word) {
            int idx = c - 'a';
            if (p->nxt[idx] == nullptr) p->nxt[idx] = new TrieNode();
            p = p->nxt[idx];
        }
        p->end = true;
    }

    bool dfs(string& word, int idx, TrieNode* cur, int cnt) {
        if (idx == word.size()) return cnt == 0 && cur->end;
        for (int i = 0; i < 26; ++i) {
            if (cur->nxt[i] == nullptr) continue;
            if (i == word[idx] - 'a') {
                if (dfs(word, idx + 1, cur->nxt[i], cnt)) return true;
            }
            else if(cnt > 0 && dfs(word, idx + 1, cur->nxt[i], cnt - 1)) return true;
        }
        return false;
    }
    
    void buildDict(vector<string> dictionary) {
        for (string& word: dictionary) add(word);
    }
    
    bool search(string searchWord) {
        return dfs(searchWord, 0, root, 1);
    }
};
  • 时间复杂度: 建立字典树 \(O(n)\), 搜索最坏情况把字典中所有单词都遍历一次，需要 \(O(nm)\)
  • 空间复杂度: \(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~