Given a string and a word dict, find all possible sentences

Question

I have been trying to figure out how to meet space and time complexity requirements for the following leet code question. I have come up with two versions, one that meets the time requirements and another that meets the space requirements. Both versions fail on the same test case (the last test case shown below). Can anyone suggest how to reconcile both space and time requirements? What am I missing?

Question and examples

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.

Example 1:

Input:

s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]

Output:

[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:

s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

Output:

[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]

Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]

Output:

[]

Code that fails time limit

class Solution:
    def wordBreak(self, s: str, wordDict: 'List[str]') -> 'List[str]':
        if not wordDict:
            return []

        wD = set(wordDict)
        max_offset = len(max(wD, key=len))
        paths = []

        def dfs(st, path):
            if st == len(s):
                paths.append(path)
                return

            for en in range(st + 1, st + max_offset + 1):
                if s[st:en] in wD:
                    dfs(en, path + [(st, en)])

        dfs(0, [])
        return [' '.join([s[x[0] : x[1]] for x in path]) for path in paths]

Code that fails space limit

class Solution:
    def wordBreak(self, s: str, wordDict: 'List[str]') -> 'List[str]':
        from collections import defaultdict

        if not wordDict:
            return []

        wD = set(wordDict)
        memo = defaultdict(list)
        memo[len(s)] = [[(len(s), len(s) + 1)]]

        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s) + 1):
                if s[i:j] in wD and j in memo:
                    for l in memo[j]:
                        memo[i].append([(i, j), *l])
        return [' '.join([s[ind[0] : ind[1]] for ind in x[:-1]]) for x in memo[0]]

Testing (the last test case fails each of the above versions)

import pprint

inps = [
    ("catsanddog", ["cat", "cats", "and", "sand", "dog"]),
    ("pineapplepenapple", ["apple", "pen", "applepen", "pine", "pineapple"]),
    ("catsandog", ["cats", "dog", "sand", "and", "cat"]),
    ("a", ['a']),
    ("abc", ['abc', 'a', 'b', 'c']),
    ("hellow", []),
    (
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
       [
           "a",
           "aa",
           "aaa",
           "aaaa",
           "aaaaa",
           "aaaaaa",
           "aaaaaaa",
           "aaaaaaaa",
           "aaaaaaaaa",
           "aaaaaaaaaa",
       ],
    ),
]

sol = Solution()
for s, wd in inps:
    print(f"Doing s[{s}] and wd[{wd}]...")
    ans = sol.wordBreak(s, wd)
    pprint.pprint(ans)

Answer 1

I have figured out how to do this problem and achieve the time and space requirements. It is faster than 64% of submissions but only more space efficient than 5% of submissions (woops). I ended up modifying the code that fails the space requirements. Here is my solution:

class Solution:
    def wordBreak(self, s: str, wordDict: 'List[str]') -> 'List[str]':
        from collections import defaultdict

        if not wordDict:
            return []

        wD = set(wordDict)
        childs = defaultdict(list)
        childs[len(s)] = [None]

        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s) + 1):
                if s[i:j] in wD and j in childs:
                    childs[i].append(j)

        paths = []

        def dfs(nd, path):
            if nd is None:
                paths.append(path)
                return

            for ch in childs[nd]:
                dfs(ch, ' '.join([path, s[nd:ch]]))

        dfs(0, '')
        return [x.strip() for x in paths]

Any optimizations are still welcome.