Description
https://leetcode.com/problems/design-add-and-search-words-data-structure/
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 <= 500wordinaddWordconsists lower-case English letters.wordinsearchconsist of'.'or lower-case English letters.- At most
50000calls will be made toaddWordandsearch.
Explanation
Create a trie to search and store words. When the word contains ‘.’, search recursively to check if next character matches.
Python Solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for c in word:
if c in node.children:
node = node.children[c]
else:
node.children[c] = TrieNode()
node = node.children[c]
node.is_word = True
def search(self, word: str) -> bool:
if not word:
return False
return self.search_helper(self.root, word, 0)
def search_helper(self, node, word, index):
if not node:
return False
if index >= len(word):
return node.is_word
char = word[index]
if char != '.':
return self.search_helper(node.children.get(char), word, index + 1)
else:
for child in node.children:
if self.search_helper(node.children[child], word, index + 1):
return True
return False
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)- Time Complexity: O(N).
- Space Complexity: O(N).