forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
add-and-search-word-data-structure-design.py
70 lines (61 loc) · 1.92 KB
/
add-and-search-word-data-structure-design.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# Time: O(min(n, h)), per operation
# Space: O(min(n, h))
#
# Design a data structure that supports the following two operations:
#
# void addWord(word)
# bool search(word)
# search(word) can search a literal word or a regular expression string
# containing only letters a-z or ..
# A . means it can represent any one letter.
#
# For example:
#
# addWord("bad")
# addWord("dad")
# addWord("mad")
# search("pad") -> false
# search("bad") -> true
# search(".ad") -> true
# search("b..") -> true
# Note:
# You may assume that all words are consist of lowercase letters a-z.
#
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.is_string = False
self.leaves = {}
class WordDictionary:
def __init__(self):
self.root = TrieNode()
# @param {string} word
# @return {void}
# Adds a word into the data structure.
def addWord(self, word):
curr = self.root
for c in word:
if c not in curr.leaves:
curr.leaves[c] = TrieNode()
curr = curr.leaves[c]
curr.is_string = True
# @param {string} word
# @return {boolean}
# Returns if the word is in the data structure. A word could
# contain the dot character '.' to represent any one letter.
def search(self, word):
return self.searchHelper(word, 0, self.root)
def searchHelper(self, word, start, curr):
if start == len(word):
return curr.is_string
if word[start] in curr.leaves:
return self.searchHelper(word, start+1, curr.leaves[word[start]])
elif word[start] == '.':
for c in curr.leaves:
if self.searchHelper(word, start+1, curr.leaves[c]):
return True
return False
# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")