# My solution using Python

• I used a Trie to store all the dict words, and then for every position i in s, find those position(s) ed so that [st, ed) is a dict word.

After that is basiclly a search problem, simply using dfs (or you can call it memorized search) to check whether from position i we can divide s[i:] with dict words.(say this array is called v, and v[i] = True if s[i:] is dividable.

If v[0] is True, then find all the solutions using recurse.

Here is my code using Python.

``````class Node:
def __init__(self):
self.next = [ None for i in range(26) ]
self.mark = False

class Solution:
# @param s, a string
# @param dict, a set of string
# @return a list of strings
def insert(self, word):
p = self.root
for s in word:
k = ord(s) - ord('a')
if p.next[k] == None:
p.next[k] = Node()
p = p.next[k]
p.mark = True

def build(self, s, st):
n = len(s)
p = self.root
for i in range(st, n):
if p == None:
return
k = ord(s[i]) - ord('a')
if p.next[k] == None:
return
p = p.next[k]
if p.mark:
self.g[st].append(i + 1)    # [st, i + 1) is a word in dict
def path(self, st):
if st == self.n:
self.v[st] = 1
return 1
if self.v[st] != -1:
return self.v[st]
for ed in self.g[st]:
if self.path(ed):
self.v[st] = 1
if self.v[st] == -1:
self.v[st] = 0
return self.v[st]

def get(self, st):
if st == self.n:
return []
res = []
for ed in self.g[st]:
if self.v[ed] == 1:
tmp = self.get(ed)
ss = self.s[st:ed]
for sp in tmp:
res.append(ss + ' ' + sp)
if tmp == []:
res.append(ss)
return res

def wordBreak(self, s, dict):
n = len(s)
self.root = Node()
self.n = n
self.s = s
#self.dict = dict
self.g = [ [] for i in range(n + 1) ]
self.v = [ -1 for i in range(n + 1) ]
for word in dict:
self.insert(word)
for i in range(n):
self.build(s, i)
ok = self.path(0)
ret = []
if ok == 1:
ret = self.get(0)
return ret``````

• My Python solution

``````import sys
import pdb

class Solution():
# @param s, a string
# @param dict, a set of string
# @return a list of strings
def wordBreak(self, s, d, curr_sentance=""):
# pdb.set_trace()
# quick check whether all chars will match (only at the begining)
if not curr_sentance:
sentance_chars = set(s)
dict_chars = set("".join(list(d)))
if not sentance_chars.issubset(dict_chars):
return []
if not s and curr_sentance:
return [curr_sentance.rstrip()]
sentances = []
for ditem in d:
if s.startswith(ditem):
sentance = self.wordBreak(s[len(ditem):], d,
curr_sentance + ditem + " ")
if sentance:
sentances += sentance

return sentances

# main ()
def main():
ph = "aaaaaaa"
d = {"aaaa", "aa", "a"}
s = Solution()
print "{}".format('\n'.join(s.wordBreak(ph, d)))
return 0

if __name__ == "__main__":
sys.exit(main())
``````

• Another python solution, this time recursive and with failures memorizations to linearize the
time complexity.

Assumes that the dictionary is huge, while the text is relatively small, is it a real case? We don't know.
There is a defect that I didn't fixed, I recalculate the max word size in the dictionary each time, this can
be done just once.

``````def _wordBreak(source, dictionary, failures, pos):
"""Splits a given text into words contained into a dictionary.

Recursive solution:
- memoizes the failures in order to avoid exponential time complexity (dynamic programming)
- first tries to match longest word in order to further reduce the number of combinations
"""

# Looks inside memoized failures to avoid exponential execution:
if pos in failures:
return None

results = []

# The entire source may be contained inside the dictionary:
if source in dictionary:
results.append([source])

# Max word size:
size = max(map(len, dictionary))   # Traverses the dictionary and looks for the longest word
size = min(len(source) - 1, size)  # Leaves at least one character for the tail.

# Tries with part of the source, first with longer ones:
while size > 0:

# Splits the source into two parts, head and tail:

# If head is not in the dictionary skips current case:
size -= 1
continue

# Continues with the tail:
tailResults = _wordBreak(tail, dictionary, failures, pos + size)
if not tailResults:
size -= 1
continue  # No solutions, skips current case.

# Collects the results after prepending the head to them:
for result in tailResults:
results.append(result)

# Tries with smaller words:
size -= 1

# On failure, memoizes it:
if len(results) == 0:
return

return results

class Solution:
"""A solution for our problem."""

def wordBreak(self, text, dictionary):
"""Splits a given text into words contained into a dictionary.

Returns a list of all possible solutions.
"""

if len(dictionary) == 0:
return []

results = _wordBreak(text, dictionary, set(), 0)
if not results:
return []

return [" ".join(result) for result in results]``````

• Another similar solution, but by embedding the recursion inside the class I obtained a slightly faster implementation, looks like that the recursive call is a bottleneck here, since now I just pass less parameters each recursion.

I also keep the max word size in the dictionary precalculated, but alone was not giving performance benefits, there was a regression because the extra parameter passed.

``````class Solution:
"""A solution for our problem."""

def __init__(self):
self.dictionary = set()
self.dictionaryMaxLen = 0
self.failures = set()

def wordBreak(self, text, dictionary):
"""Splits a given text into words contained into a dictionary.

Returns a list of all possible solutions.
"""

if len(dictionary) == 0:
return []

# Prepares the object for the recursive execution:
self.dictionary = dictionary
self.dictionaryMaxLen = max(map(len, dictionary))
self.failures = set()

results = self._wordBreak(text, 0)
if not results:
return []

return [" ".join(result) for result in results]

def _wordBreak(self, source, pos):
"""Splits a given text into words contained into a dictionary.

Returns a list of all possible solutions or None in case of failure.

Recursive solution:
- memoizes the failures in order to avoid exponential time complexity (dynamic programming)
- first tries to match longest word in order to further reduce the number of combinations
"""

# Looks inside memoized failures to avoid exponential execution:
if pos in self.failures:
return None

results = []

# The entire source may be contained inside the dictionary:
if source in self.dictionary:
results.append([source])

# Max word size:
size = min(len(source) - 1, self.dictionaryMaxLen)  # Leaves at least one character for the tail.

# Tries with part of the source, first with longer ones:
while size > 0:

# Splits the source into two parts, head and tail:

# If head is not in the dictionary skips current case:
size -= 1
continue

# Continues with the tail:
tailResults = self._wordBreak(tail, pos + size)
if not tailResults:
size -= 1
continue  # No solutions, skips current case.

# Collects the results after prepending the head to them:
for result in tailResults:
results.append(result)

# Tries with smaller words:
size -= 1

# On failure, memoizes it:
if len(results) == 0: