# Split a string into valid words

I am trying to solve this LeetCode question:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

I have a solution that works correctly but exceeds python's memory limit on large inputs.

Note that the Solution class is required by LeetCode's interface.

from collections import defaultdict
class Solution:
def wordBreak(self, s, wordDict):
cache = defaultdict(list)
word_dict = set(wordDict)
def partition(s):
if s in cache:
return cache[s]
res = []
if s in word_dict:
res.append(s)
for i in range(1, len(s)):
words = partition(s[i:])
k = s[:i]
if k in word_dict:
for word in words:
res.append(k +" "+word)

cache[s] = res
return res
return partition(s)



How do I optimize it in terms of space complexity?

Please refrain from commenting that the function doesn't have to be a method bound to the class instance. It cannot be changed as it is the template used to run the solution.

• @bullseye This might have been a copy paste error since the only error is missing the import statement. I edited the question, but anyone let me know if this change deviates from the authors intent (in my opinion it doesn't) and the edit will be rolled back accordingly. – Linny Oct 5 at 5:41
• @bullseye: It is allowed (and in fact, expected) to update the question with working code. What you must not do is to modify the code after answers have been posted. – Martin R Oct 5 at 7:37
• @bullseye: My comment was only addressed to your remark that “it's not allowed ... to edit the code if it's not working” which is wrong. Of course you are free to flag the question if you think that it is not working. – In this case however the code is (allegedly) working in the context of LeetCode, so that would (in my opinion) count as “working to the best knowledge of the author.” – Martin R Oct 5 at 10:26
• @nz_21: I understand what you mean. However, as a convenience to the possible reviewers, you could add the necessary imports and a (minimal) main program to make the code runnable on its own. – Martin R Oct 5 at 10:28
• @bullseye: I get your point (and you are free to review the challenge requirements), but I don't agree that it makes the question itself off-topic (my opinion :) – Martin R Oct 5 at 15:23