单词拆分 II
- 难度： 困难
- 通过率： 26.2%
- 题目链接：https://leetcode-cn.com/problems/word-break-ii
题目描述
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
- 分隔时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "catsanddog" wordDict =["cat", "cats", "and", "sand", "dog"]输出:[ "cats and dog", "cat sand dog" ]
示例 2：
输入: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] 输出: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] 解释: 注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: []
解法：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
words = set(wordDict)
if not self.can_break(s, words):
return []
dp = [['']] + [[] for _ in s]
for i in range(1, len(s)+1):
for j in range(0, i):
if dp[j] and s[j:i] in words:
for sub in dp[j]:
if sub:
sub = sub + ' '
dp[i].append(sub + s[j:i])
return dp[-1]
def can_break(self, s, words):
dp = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
for j in range(0, i):
if dp[j] and s[j:i] in words:
dp[i] = True
break;
return dp[-1]
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> words = unordered_set<string>(wordDict.begin(), wordDict.end());
if(!this->can_break(s, words)){
return vector<string> ret(0);
}
vector<vector<string>> dp(s.size()+1);
dp[0].push_back("");
for(size_t i=1;i<=s.size();i++){
for(size_t j=0;j<i;j++){
string word = s.substr(j, i-j);
if(dp[j].size() > 0 && words.find(word) != words.end()){
for(string sub: dp[j]){
if(!sub.empty()){
sub += " ";
}
dp[i].push_back(sub + word);
}
}
}
}
return dp[s.size()];
}
bool can_break(string s, unordered_set<string>& words){
vector<bool> dp(s.size()+1);
dp[0] = true;
for(size_t i = 1; i<=s.size();i++){
for(size_t j=0;j<i;j++){
string word = s.substr(j, i-j);
if(dp[j] && words.find(word) != words.end()){
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};