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 <= 25 -
wordinaddWordconsists of lowercase English letters. -
wordinsearchconsist of'.'or lowercase English letters. - There will be at most
3dots inwordforsearchqueries. - At most
104calls will be made toaddWordandsearch.
SOLUTION:
class Node:
def __init__(self, val=None, children=[], end=False):
self.val = val
self.children = children
self.end = end
class WordDictionary:
def __init__(self):
self.root = Node(val=None, children=[])
def addWord(self, word: str) -> None:
n = len(word)
curr = self.root
for i, c in enumerate(word):
found = False
for node in curr.children:
if node.val == c:
curr = node
found = True
break
if not found:
newcurr = Node(val=c, children=[])
curr.children.append(newcurr)
curr = newcurr
curr.end = True
def search(self, word: str) -> bool:
n = len(word)
paths = [(self.root, 0)]
while len(paths) > 0:
curr, i = paths.pop()
if i == n and curr.end:
return True
if curr.children and i < n:
for c in curr.children:
if word[i] == "." or c.val == word[i]:
paths.append((c, i + 1))
return False
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
Top comments (0)