-
Notifications
You must be signed in to change notification settings - Fork 0
/
wordbreak.py
120 lines (95 loc) · 3.12 KB
/
wordbreak.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
""" Given a string without spaces and a dictionary return or print all
possible ways that the string can be broken so that only valid words are
formed.
Eg. "programmerit", dict = { "pro", "gram", "merit", "program", "programmer",
"it" }
{"pro", "gram", "merit"}, {"program", "merit"}, {"programmer", "it"}
"""
class TrieNode(object):
def __init__(self, data, end=False):
self.data = data
self.end = end
self.children = {}
def has_child(self, child):
return child in self.children
def get_child(self, child):
return self.children[child]
def get_children(self):
return self.children.values()
def add_child(self, child):
if child in self.children:
raise ValueError("Child already present.")
self.children[child] = TrieNode(child)
return self.children[child]
def __str__(self):
return '<{} (end: {}, children: {})>'.format(self.data,
self.end,
self.children.keys())
class Trie(object):
def __init__(self):
self.root = TrieNode('.')
def add_word(self, word):
node = self.root
for char in word:
if node.has_child(char):
node = node.get_child(char)
else:
node = node.add_child(char)
node.end = True
def add_words(self, words):
for word in words:
self.add_word(word)
def has_word(self, word):
node = self.root
for char in word:
if node.has_child(char):
node = node.get_child(char)
else:
return False
return node.end
def __str__(self):
queue = [self.root]
str_ = ""
while len(queue) > 0:
node = queue.pop()
queue.extend(node.get_children())
str_ += str(node) + str(node.get_children()) + "\n"
return str_
# def is_word_in_trie(word, trie):
# answer = []
# word_added = False
# for idx, _ in enumerate(word):
# if trie.has_word(word[:idx+1]):
# answer.append(word[:idx+1])
# result = is_word_in_trie(word[idx+1:], trie)
# if result:
# answer.extend(result)
# if word_added:
# return answer
def word_break(word, trie):
answer = []
for idx, char in enumerate(word):
word_added = False
current = []
if trie.has_word(word[:idx+1]):
word_added = True
current.append(word[:idx+1])
result = word_break(word[idx+1:], trie)
if result:
current.extend(result)
if word_added:
answer.append(current)
# print word, current
if len(answer) == 1:
return answer[0]
else:
return answer
if __name__ == '__main__':
trie = Trie()
words = ["pro", "gram", "merit", "program", "programmer", "it"]
trie.add_words(words)
for word in words:
print word, trie.has_word(word)
# print trie
print "&" * 80
print word_break('programmerits', trie)