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

First of all, this problem is extention of problem 139. Word Break, where we need just to check if word can be broken into other words. Here we need to give all possible splits. Let us first put all words into set and create two lists:

  1. dp_solution[i] is all possible splits for first i symbols of s
  2. dp[i] is indicator if we can split word or not.

Also we create this two lists with size (n+1) to handle border cases, in dp[-1] we will keep result for empty string "".

  1. First step is to check if our string can be splitted at all, using problem 139. We need to do it, to candle strings like aaaaa...aaab, with wordDict = [a, aa, aaa, ..., aa..aa]. In this case answer will be no, but if we try to build solution directly we will get MLE. Try to remove this lines of code from solution and you will see.
  2. Now, we do one more pass over data and start to build solutions: if we found that s[j: k + 1] in wordSet, then for every already built solution sol in dp_solution[j-1] we can add it to dp_solution[k].
  3. Finally, we have some extraspaces in the beginning of each solution, and instead of last element [-1] we need to return previous [-2], so we return return [s[1:] for s in dp_solution[-2]]

Complexity: to create dp we need O(n^2m) time, where m is average length of word and O(n^2) space. However for dp_solution part we can have potentially exponential number of solutions, for example even for s = aa.....aa, wordDict = [a, aa]. I think leetcode just will not give you tests, where memory will exceed some limit.

class Solution:
    def wordBreak(self, s, wordDict):
        wordSet = set(wordDict)
        n = len(s)
        dp_solution = [[] for _ in range(n)] + [[""]]
        dp = [0] * n + [1]
        
        for k in range(n):
            for j in range(k,-1,-1):
                if s[j: k + 1] in wordSet:
                    dp[k] = max(dp[k], dp[j-1])

        if dp[-2] == 0: return []

        for k in range(n):
            for j in range(k,-1,-1):
                if s[j: k + 1] in wordSet:
                    for sol in dp_solution[j-1]:
                        dp_solution[k].append(sol + " " + s[j: k + 1])
                        
        return [s[1:] for s in dp_solution[-2]]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0140