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:[]
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
wordDict =set(wordDict)
check={}
def wordBreak(s):
if s in check:
return check[s]
res=[]
if s in wordDict:
res.append(s)
for i in range(1,len(s)):
if s[i:] in wordDict:
for w in wordBreak(s[0:i]):
res += [w + " " + s[i:] ]
check[s]=res
#print(check[s])
return check[s]
return wordBreak(s)
From the beginning of string, iterate to the end, once we found the right parts is in the dictionary.
Recursively called the method with the left part, till we found none.
Append all result in the right part to possible combination of the left part
Return answer.
First check:
s[7:]:dog
(swaped) For sand till left, there is combination cat + sand
s[3:]:sand
check[cat]['cat']
(swaped) and we found and with cats + and
s[4:]:and
check[cats]['cats']
got the both combination for catsand
check[catsand]['cat sand', 'cats and']
gor the all possible comnation for s
check[catsanddog]['cat sand dog', 'cats and dog']
请登录之后再进行评论