Word break II

Problem:

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.

Input and output examples

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.

Solution

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """        
        dp = [None] * (len(s) + 1)
        dp[0] = ['']
        for i in range(1, len(s) + 1):
            dp[i] = []
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    for word in dp[j]:
                        dp[i].append(word + (' ' if word else '') + s[j:i])
        return dp[-1]

Test the the solution:

s = "catsanddog"
wordDict = ["cat","cats","and","sand","dog"]
print(Solution().wordBreak(s, wordDict))

More interview questions can be found here:
Algorithm