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.
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.