# 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 ```