Word break II


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


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.


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:

Author: robot learner
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source robot learner !