Ytdyklly

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)