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:
[]
139. Word Break 的拓展，那道题只是让判断是否可以拆分，而这道题要求输出所有可能的拆分组合。
解法：dp + dfs，先用dp计算是否可以拆分，然后用dfs求出具体拆分的组合。
Java:
public static List<String> wordBreak(String s, Set<String> dict) {
//create an array of ArrayList<String>
List<String> dp[] = new ArrayList[s.length()+1];
dp[0] = new ArrayList<String>();
for(int i=0; i<s.length(); i++){
if( dp[i] == null )
continue;
for(String word:dict){
int len = word.length();
int end = i+len;
if(end > s.length())
continue;
if(s.substring(i,end).equals(word)){
if(dp[end] == null){
dp[end] = new ArrayList<String>();
}
dp[end].add(word);
}
}
}
List<String> result = new LinkedList<String>();
if(dp[s.length()] == null)
return result;
ArrayList<String> temp = new ArrayList<String>();
dfs(dp, s.length(), result, temp);
return result;
}
public static void dfs(List<String> dp[],int end,List<String> result, ArrayList<String> tmp){
if(end <= 0){
String path = tmp.get(tmp.size()-1);
for(int i=tmp.size()-2; i>=0; i--){
path += " " + tmp.get(i) ;
}
result.add(path);
return;
}
for(String str : dp[end]){
tmp.add(str);
dfs(dp, end-str.length(), result, tmp);
tmp.remove(tmp.size()-1);
}
}
Java:
public List<String> wordBreak(String s, Set<String> wordDict) {
ArrayList<String> [] pos = new ArrayList[s.length()+1];
pos[0]=new ArrayList<String>();
for(int i=0; i<s.length(); i++){
if(pos[i]!=null){
for(int j=i+1; j<=s.length(); j++){
String sub = s.substring(i,j);
if(wordDict.contains(sub)){
if(pos[j]==null){
ArrayList<String> list = new ArrayList<String>();
list.add(sub);
pos[j]=list;
}else{
pos[j].add(sub);
}
}
}
}
}
if(pos[s.length()]==null){
return new ArrayList<String>();
}else{
ArrayList<String> result = new ArrayList<String>();
dfs(pos, result, "", s.length());
return result;
}
}
public void dfs(ArrayList<String> [] pos, ArrayList<String> result, String curr, int i){
if(i==0){
result.add(curr.trim());
return;
}
for(String s: pos[i]){
String combined = s + " "+ curr;
dfs(pos, result, combined, i-s.length());
}
}
Java:
public class Solution {
Map<String, List<String>> done = new HashMap<>();
Set<String> dict;
public List<String> wordBreak(String s, Set<String> dict) {
this.dict = dict;
done.put("", new ArrayList<>());
done.get("").add("");
return dfs(s);
}
List<String> dfs(String s) {
if (done.containsKey(s)) {
return done.get(s);
}
List<String> ans = new ArrayList<>();
for (int len = 1; len <= s.length(); len++) {
String s1 = s.substring(0, len);
String s2 = s.substring(len);
if (dict.contains(s1)) {
List<String> s2_res = dfs(s2);
for (String item : s2_res) {
if (item == "") {
ans.add(s1);
} else {
ans.add(s1 + " " + item);
}
}
}
}
done.put(s, ans);
return ans;
}
}
Python:
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
n = len(s) max_len = 0
for string in wordDict:
max_len = max(max_len, len(string)) can_break = [False for _ in xrange(n + 1)]
valid = [[False] * n for _ in xrange(n)]
can_break[0] = True
for i in xrange(1, n + 1):
for l in xrange(1, min(i, max_len) + 1):
if can_break[i-l] and s[i-l:i] in wordDict:
valid[i-l][i-1] = True
can_break[i] = True result = []
if can_break[-1]:
self.wordBreakHelper(s, valid, 0, [], result)
return result def wordBreakHelper(self, s, valid, start, path, result):
if start == len(s):
result.append(" ".join(path))
return
for i in xrange(start, len(s)):
if valid[start][i]:
path += [s[start:i+1]]
self.wordBreakHelper(s, valid, i + 1, path, result)
path.pop()
C++:
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> res;
string out;
vector<bool> possible(s.size() + 1, true);
wordBreakDFS(s, wordDict, 0, possible, out, res);
return res;
}
void wordBreakDFS(string &s, unordered_set<string> &wordDict, int start, vector<bool> &possible, string &out, vector<string> &res) {
if (start == s.size()) {
res.push_back(out.substr(0, out.size() - 1));
return;
}
for (int i = start; i < s.size(); ++i) {
string word = s.substr(start, i - start + 1);
if (wordDict.find(word) != wordDict.end() && possible[i + 1]) {
out.append(word).append(" ");
int oldSize = res.size();
wordBreakDFS(s, wordDict, i + 1, possible, out, res);
if (res.size() == oldSize) possible[i + 1] = false;
out.resize(out.size() - word.size() - 1);
}
}
}
};
类似题目：
[LeetCode] 139. Word Break 单词拆分