• 注册

• 今日签到
• 连续签到

暂没有数据

暂没有数据

• 查看作者
• # LeetCode 140. Word Break II

140. Word Break II
Hard

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

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']

纽约州·法拉盛
• 0
• 0
• 0
• 206