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

  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Linny
    Oct 5, 2019 at 5:41
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – Martin R
    Oct 5, 2019 at 7:37
  • 1
    \$\begingroup\$ @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.” \$\endgroup\$
    – Martin R
    Oct 5, 2019 at 10:26
  • 3
    \$\begingroup\$ @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. \$\endgroup\$
    – Martin R
    Oct 5, 2019 at 10:28
  • 1
    \$\begingroup\$ @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 :) \$\endgroup\$
    – Martin R
    Oct 5, 2019 at 15:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.