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.
