forked from Firkraag/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
WordDictionary_211.py
91 lines (83 loc) · 2.53 KB
/
WordDictionary_211.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#!/usr/bin/env python
# coding=utf-8
class TrieNode(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.child = [None] * 26
self.char = None
self.freq = 0
self.indices = set()
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
node = self.root
for char in word:
index = ord(char) - ord('a')
if node.child[index] == None:
child = TrieNode()
child.char = char
node.indices.add(index)
node.child[index] = child
node = child
else:
node = node.child[index]
node.freq += 1
class WordDictionary(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.trie = Trie()
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
self.trie.insert(word)
def search(self, word):
"""
Returns if the word is in the data structure. A word could
contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
node = self.trie.root
return self._search(word, 0, len(word) - 1, node)
for char in word:
if char == '.':
return self.s
else:
index = ord(char) - ord('a')
if node.child[index] == None:
return False
else:
node = node.child[index]
return node.freq > 0
def _search(self, word, start, end, node):
if start > end:
return node.freq > 0
char = word[start]
if char == '.':
for index in node.indices:
if self._search(word, start + 1, end, node.child[index]):
return True
return False
else:
index = ord(char) - ord('a')
if node.child[index] == None:
return False
else:
return self._search(word, start + 1, end, node.child[index])
# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")