211. Design Add and Search Words Data Structure
leetcode medium
Task
Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.
Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.
Пример:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
C# solution
matched/originalusing System.Collections.Generic;
class TrieNode {
public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
public bool IsWord = false;
}
class WordDictionary {
private TrieNode trie;
public WordDictionary() {
trie = new TrieNode();
}
public void AddWord(string word) {
TrieNode node = trie;
foreach (char ch in word) {
if (!node.Children.ContainsKey(ch)) {
node.Children[ch] = new TrieNode();
}
node = node.Children[ch];
}
node.IsWord = true;
}
private bool SearchInNode(string word, TrieNode node) {
for (int i = 0; i < word.Length; i++) {
char ch = word[i];
if (!node.Children.ContainsKey(ch)) {
if (ch == '.') {
foreach (var child in node.Children.Values) {
if (SearchInNode(word.Substring(i + 1), child)) {
return true;
}
}
}
return false;
} else {
node = node.Children[ch];
}
}
return node.IsWord;
}
public bool Search(string word) {
return SearchInNode(word, trie);
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class TrieNode {
public unordered_map<char, TrieNode> Children = new unordered_map<char, TrieNode>();
public bool IsWord = false;
}
class WordDictionary {
private TrieNode trie;
public WordDictionary() {
trie = new TrieNode();
}
public void AddWord(string word) {
TrieNode node = trie;
foreach (char ch in word) {
if (!node.Children.count(ch)) {
node.Children[ch] = new TrieNode();
}
node = node.Children[ch];
}
node.IsWord = true;
}
private bool SearchInNode(string word, TrieNode node) {
for (int i = 0; i < word.size(); i++) {
char ch = word[i];
if (!node.Children.count(ch)) {
if (ch == '.') {
foreach (var child in node.Children.Values) {
if (SearchInNode(word.Substring(i + 1), child)) {
return true;
}
}
}
return false;
} else {
node = node.Children[ch];
}
}
return node.IsWord;
}
public bool Search(string word) {
return SearchInNode(word, trie);
}
}Java solution
matched/originalclass TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean word = false;
public TrieNode() {}
}
class WordDictionary {
TrieNode trie;
public WordDictionary() {
trie = new TrieNode();
}
public void addWord(String word) {
TrieNode node = trie;
for (char ch : word.toCharArray()) {
if (!node.children.containsKey(ch)) {
node.children.put(ch, new TrieNode());
}
node = node.children.get(ch);
}
node.word = true;
}
public boolean searchInNode(String word, TrieNode node) {
for (int i = 0; i < word.length(); ++i) {
char ch = word.charAt(i);
if (!node.children.containsKey(ch)) {
if (ch == '.') {
for (char x : node.children.keySet()) {
TrieNode child = node.children.get(x);
if (searchInNode(word.substring(i + 1), child)) {
return true;
}
}
}
return false;
} else {
node = node.children.get(ch);
}
}
return node.word;
}
public boolean search(String word) {
return searchInNode(word, trie);
}
}JavaScript solution
matched/originalclass TrieNode {
constructor() {
this.children = new Map();
this.isWord = false;
}
}
class WordDictionary {
constructor() {
this.trie = new TrieNode();
}
addWord(word) {
let node = this.trie;
for (let ch of word) {
if (!node.children.has(ch)) {
node.children.set(ch, new TrieNode());
}
node = node.children.get(ch);
}
node.isWord = true;
}
searchInNode(word, node) {
for (let i = 0; i < word.length; i++) {
let ch = word[i];
if (!node.children.has(ch)) {
if (ch === '.') {
for (let child of node.children.values()) {
if (this.searchInNode(word.slice(i + 1), child)) {
return true;
}
}
}
return false;
} else {
node = node.children.get(ch);
}
}
return node.isWord;
}
search(word) {
return this.searchInNode(word, this.trie);
}
}Python solution
matched/originalclass WordDictionary:
def __init__(self):
self.trie = {}
def addWord(self, word: str) -> None:
node = self.trie
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
node["$"] = True
def search(self, word: str) -> bool:
def search_in_node(word, node) -> bool:
for i, ch in enumerate(word):
if ch not in node:
if ch == ".":
for x in node:
if x != "$" and search_in_node(word[i + 1:], node[x]):
return True
return False
else:
node = node[ch]
return "$" in node
return search_in_node(word, self.trie)Go solution
matched/originalpackage main
type TrieNode struct {
children map[rune]*TrieNode
isWord bool
}
type WordDictionary struct {
root *TrieNode
}
func Constructor() WordDictionary {
return WordDictionary{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}
func (this *WordDictionary) AddWord(word string) {
node := this.root
for _, ch := range word {
if _, ok := node.children[ch]; !ok {
node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
}
node = node.children[ch]
}
node.isWord = true
}
func (this *WordDictionary) searchInNode(word string, node *TrieNode) bool {
for i, ch := range word {
if nextNode, ok := node.children[ch]; ok {
node = nextNode
} else {
if ch == '.' {
for _, child := range node.children {
if this.searchInNode(word[i+1:], child) {
return true
}
}
}
return false
}
}
return node.isWord
}
func (this *WordDictionary) Search(word string) bool {
return this.searchInNode(word, this.root)
}
func main() {
wordDictionary := Constructor()
wordDictionary.AddWord("bad")
wordDictionary.AddWord("dad")
wordDictionary.AddWord("mad")
println(wordDictionary.Search("pad")) // Output: false
println(wordDictionary.Search("bad")) // Output: true
println(wordDictionary.Search(".ad")) // Output: true
println(wordDictionary.Search("b..")) // Output: true
}Explanation
Algorithm
1️⃣
Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.
2️⃣
Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.
3️⃣
Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.
😎