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:
[]
My code:
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
slen = len(s)
wordDict = set(wordDict)
# saves the solutions for previous recursion calls:
solvedFs = [None for _ in range(slen)]
# Recursion function:
def F(i):
# F(i) = breaks for the string s[i:]
# check if already solved F(i):
if solvedFs[i] is not None:
return solvedFs[i]
breaks = []
for j in range(i+1, slen+1):
# check if the prefix of current string is in dict:
w = s[i:j]
if w in wordDict:
if j == slen:
# found the final word:
breaks += [w]
else:
# add the current word to all possible future breaks:
nextBreaks = F(j)
for b in nextBreaks:
breaks += [w + " " + b]
solvedFs[i] = breaks
return breaks
return F(0)
def wordBreak1(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
if len(s)==0:
return []
self.min_len=10000000000
self.len_dict=set()
wordDict=set(wordDict)
for item in wordDict:
if len(item)<self.min_len:
self.min_len=len(item)
if len(item) not in self.len_dict:
self.len_dict.add(len(item))
print(self.len_dict)
record=self.Look_Through(s,0,wordDict)
if record==None:
return []
return list(record)
def Look_Through(self,s,i,wordDict):
if i==len(s):
return [""]
if s[i:] in wordDict and len(s)-i==self.min_len:
tmp_Record=set()
tmp_Record.add(s[i:])
return tmp_Record
if len(s)-i<self.min_len:
return None
record=set()
for length in self.len_dict:
#print('checked str %s, i %d'%(s[i:i+length],i))
if s[i:i+length] in wordDict:
tmp_record=self.Look_Through(s,i+length,wordDict)
if tmp_record!=None:
for item in tmp_record:
if item=="":
record.add(s[i:i+length]+item)
else:
record.add(s[i:i+length]+' '+item)
return record