動機
就是backtrack
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.
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
andwordDict[i]
consist of only lowercase English letters.- All the strings of
wordDict
are unique.
Sol
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
def bt(s,acc):
if not s:
return [acc[1:]] # remove leading space
else:
ret = []
for i in range(1,len(s)+1):
if s[:i] in wordDict:
ret += bt(s[i:], f"{acc} {s[:i]}")
return ret
return bt(s, "")