0211-design-add-and-search-words-data-structure¶
Try it on leetcode
Description¶
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary()Initializes the object.void addWord(word)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay contain dots'.'where dots can be matched with any letter.
Example:
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
Constraints:
1 <= word.length <= 25wordinaddWordconsists of lowercase English letters.wordinsearchconsist of'.'or lowercase English letters.- There will be at most
2dots inwordforsearchqueries. - At most
104calls will be made toaddWordandsearch.
Solution(Python)¶
from dataclasses import dataclass, field
from typing import Dict
@dataclass
class TrieNode:
val: str = ""
children: Dict[str, 'TrieNode'] = field(default_factory= dict)
isEnd: bool = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
cur_node = self.root
for ch in word:
if ch not in cur_node.children:
cur_node.children[ch] = TrieNode(ch)
cur_node = cur_node.children[ch]
cur_node.isEnd = True
def search(self, word: str) -> bool: #
return self.dfs(0, self.root, word)
def dfs(self, index, node, word):
cur_node = node
for i in range(index, len(word)):
ch = word[i]
if ch == '.':
return self.wildcardmatch(cur_node, i, word)
elif ch not in cur_node.children:
return False
else:
cur_node = cur_node.children[ch]
return cur_node.isEnd
def wildcardmatch(self, cur_node, i, word):
for child in cur_node.children.values():
if self.dfs(i+1, child, word):
return True
return False
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)