0140. Word Break II.py

# 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: []
#
# Constraints:
#
# 1 <= s.length <= 20
# 1 <= wordDict.length <= 1000
# 1 <= wordDict[i].length <= 10
# s and wordDict[i] consist of only lowercase English letters.
# All the strings of wordDict are unique.


# Backtracking + Memoization
# Similar
# 139. Word Break
# 140. Word Break II
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        dic = {}

        def go(s: str) -> List[str]:
            if s in dic:
                return dic[s]
            if not s:
                return []

            res = []
            for w in wordDict:
                if s.startswith(w):
                    s2 = s[len(w) :]
                    if not s2:
                        res.append(w)
                    else:
                        # res += [w + " " + x for x in go(s2)]
                        res.extend([w + " " + x for x in go(s2)])
            dic[s] = res
            return res

        return go(s)