0
\$\begingroup\$

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.

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.

https://leetcode.com/problems/word-break-ii/

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:
                words.append(s[i:])

            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 
                        words.append(new)

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

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

\$\endgroup\$
  • \$\begingroup\$ How long is the string that times out ? \$\endgroup\$ – Gloweye Oct 25 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 at 9:56
  • \$\begingroup\$ You may consider to accept some answers if there helped. \$\endgroup\$ – Martin R Oct 25 at 10:01
  • \$\begingroup\$ @MartinR done :) \$\endgroup\$ – nz_21 Oct 25 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.