Word Break 2

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

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: []

from typing import List
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordSet = set(wordDict)
        def wordBreakBacktrack(i):
          if i == len(s):
            return [[]]
          res = []
          for j in range(i, len(s)+1):
            substr = s[i:j+1]
            if substr in wordSet:
              for word in wordBreakBacktrack(j+1):
                res.append([substr] + word)
          return res
        return [" ".join(word) for word in wordBreakBacktrack(0)]

Solution().wordBreak("catsanddog", ["cat","cats","and","sand","dog"])

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