I am trying to solve this 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.


My working code that times out:

class Solution:
    def wordBreak(self, s, word_set) :
        cache = {}
        word_set = set(word_set)
        def dfs(i):
            if i in cache:
                return cache[i]

            words = []
            res = ""
            if s[i:] in word_set:

            for k in range(i, len(s)):
                res += s[k]
                next_words = dfs(k+1)
                if res in word_set:
                    for w in next_words:
                        new = res + " "+w 

            cache[i] = words 
            return words 
        return dfs(0)

How do I optimize this in terms of time and space complexity?

  • \$\begingroup\$ How long is the string that times out ? \$\endgroup\$ – Gloweye Oct 25 '19 at 9:55
  • 1
    \$\begingroup\$ Also, please note that the leetcode idea of putting every function into a class named "Solution" is very bad practice. It really should be a function, not a class. \$\endgroup\$ – Gloweye Oct 25 '19 at 9:56
  • \$\begingroup\$ You may consider to accept some answers if there helped. \$\endgroup\$ – Martin R Oct 25 '19 at 10:01
  • \$\begingroup\$ @MartinR done :) \$\endgroup\$ – nz_21 Oct 25 '19 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.