题目描述
实现一个带有 buildDict
, 以及 search
方法的魔法字典。
对于 buildDict
方法,你将被给定一些不重复的单词来构建一个字典。
对于 search
方法,你将被给定一个单词,并且判定能否只将这个单词中一个字母换成另一个字母(不能是相同的字母),使得所形成的新单词存在于你构建的字典中。
样例
输入:
buildDict(["hello", "leetcode"])
search("hello")
search("hhllo")
search("hell")
search("leetcoded")
输出:
[null, false, true, false, false]
提示
- 你可以假设所有输入都是小写字母
a-z
。
算法
(字典树 / Trie + 宽度优先遍历 / BFS) 初始化 $O(S)$;查询 $O(S)$
- 初始化时,创建一棵字典树,存放所有单词。
- 查询时,我们通过宽度优先遍历的方式,队列中的每个状态记录一个三元组
(index, modified, Node)
,即当前对应待查询单词的下标,是否修改过以及处于字典树中哪个结点。 - 拓展结点时,根据是否已经修改过来确定入队的结点。
时间复杂度
- 插入的时间复杂度就是遍历所有字符的时间复杂度。
- 查询时,最坏情况下,每一层都有可能扩展到所有的结点,所以时间复杂度仍然为字典树的所有结点,但常数会非常小。
空间复杂度
- 空间最多为所有字符的数量,即 $O(S)$。
C++ 代码
struct Node {
Node *nxt[26];
bool is_word;
Node() {
memset(nxt, 0, sizeof(nxt));
is_word = false;
}
};
class MagicDictionary {
public:
/** Initialize your data structure here. */
Node *root;
MagicDictionary() {
root = new Node();
}
/** Build a dictionary through a list of words */
void buildDict(vector<string> dict) {
for (const auto &s : dict) {
Node *p = root;
for (char c : s) {
if (!(p -> nxt[c - 'a']))
p -> nxt[c - 'a'] = new Node();
p = p -> nxt[c - 'a'];
}
p -> is_word = 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) {
queue<tuple<int, bool, Node*>> q;
q.push(make_tuple(0, false, root));
while (!q.empty()) {
auto u = q.front();
q.pop();
Node *cur = get<2>(u);
if (get<0>(u) == word.size()) {
if (get<1>(u) && cur -> is_word)
return true;
continue;
}
int c = word[get<0>(u)] - 'a';
if (!get<1>(u)) {
for (int i = 0; i < 26; i++)
if (cur -> nxt[i] && c != i)
q.push(make_tuple(get<0>(u) + 1, true, cur -> nxt[i]));
}
if (cur -> nxt[c])
q.push(make_tuple(get<0>(u) + 1, get<1>(u), cur -> nxt[c]));
}
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);
*/