class MyNode object def __init__ self ch self _data self _ch ch self i

 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
class MyNode(object):
def __init__(self, ch):
self._data = {}
self._ch = ch
self.is_end = False
def __str__(self):
is_end = 'T' if self.is_end else 'F'
return '[' + self._ch + '-> '+ ','.join(list(self._data.keys())) + is_end + ']'
def get_child(self, ch):
if ch in self._data:
return self._data[ch]
else:
return None
def add(self, ch):
if ch in self._data:
return self._data[ch]
child = MyNode(ch)
self._data[ch] = child
return child
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
n = len(s)
root = MyNode(' ')
for word in wordDict:
temp = root
for ch in word:
temp = temp.add(ch)
temp.is_end = True
r = [[] for _ in range(n+1)]
r[0] = [-1]
for ind in range(n):
if not r[ind]:
continue
temp = root
j = ind
while j < n and temp:
temp = temp.get_child(s[j])
if temp and temp.is_end:
r[j+1].append(ind)
# print(s[:j+1])
j += 1
spaces = [[] for _ in range(n+1)]
# print(r)
if not r[n]:
return []
spaces[n] = [[x] for x in r[n]]
result = []
for i in range(n, 0, -1):
if not spaces[i]:
continue
for arr in spaces[i]:
prev = arr[len(arr) - 1]
for el in r[prev]:
if el == -1:
result.append(arr[:])
else:
spaces[el].append(arr[:] + [el] )
r = []
# print(result)
for arr in spaces[0]:
rs = s
for el in arr[:-1]:
rs = rs[:el] + ' ' + rs[el:]
r.append(rs)
if result:
r.append(s)
return r