設計一個數據結構來支持添加新單詞並查找字符串是否與任何之前添加的字符串匹配。
實現 WordDictionary 類：WordDictionary(): 初始化對象。
void addWord(word): 將單詞添加到數據結構中，它可以在之後被匹配。
bool search(word): 如果數據結構中有任何字符串與給定單詞匹配，則返回 true，否則返回 false。單詞可能包含點 .，其中點可以匹配任何字母。
範例：
輸入：["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
輸出：[null,null,null,null,false,true,true,true]
解釋：WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // 返回 False wordDictionary.search("bad"); // 返回 True wordDictionary.search(".ad"); // 返回 True wordDictionary.search("b.."); // 返回 True
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
def search_in_node(word, node):
for i, char in enumerate(word):
if char == '.':
for child in node.children.values():
if search_in_node(word[i+1:], child):
return True
return False
else:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
return search_in_node(word, self.root)
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
64.22MB, 1546ms
C++
#include <unordered_map>
#include <string>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool is_end_of_word;
TrieNode() : is_end_of_word(false) {}
};
class WordDictionary {
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->is_end_of_word = true;
}
bool search(string word) {
return searchInNode(word, root);
}
private:
TrieNode* root;
bool searchInNode(string word, TrieNode* node) {
for (int i = 0; i < word.size(); ++i) {
char c = word[i];
if (c == '.') {
for (auto& child : node->children) {
if (searchInNode(word.substr(i + 1), child.second)) {
return true;
}
}
return false;
} else {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
}
return node->is_end_of_word;
}
};
545.44MB, 931ms
Javascript
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
var WordDictionary = function() {
this.root = new TrieNode();
};
/**
* @param {string} word
* @return {void}
*/
WordDictionary.prototype.addWord = function(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
};
/**
* @param {string} word
* @return {boolean}
*/
WordDictionary.prototype.search = function(word) {
const searchInNode = (word, node) => {
for (let i = 0; i < word.length; i++) {
const char = word[i];
if (char === '.') {
for (const key in node.children) {
if (searchInNode(word.slice(i + 1), node.children[key])) {
return true;
}
}
return false;
} else {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
}
return node.isEndOfWord;
};
return searchInNode(word, this.root);
};
90.19MB, 962ms
