LeetCode - Word Break II
Problem description
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:
1 2 3 4 5 6 7 8
Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ]
Example 2:
1 2 3 4 5 6 7 8 9 10
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:
1 2 3 4 5
Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []
Analysis
Basically, it’s the same for word break, we can use backtrack and memorization to solve this.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> res = new ArrayList<>();
HashSet<String> set = new HashSet<>(wordDict);
backtrack(res, new ArrayList<>(), 0, set, s);
return res;
}
void backtrack(List<String> res, List<String> list, int start, HashSet<String> set, String s){
if (start == s.length()){
String str = "";
for (String word:list){
str+=word;
str+=" ";
}
res.add(str.substring(0, str.length() - 1));
return;
}
for (int i = start+1; i<= s.length() ;i++){
if (!failed.contains(i) && set.contains(s.substring(start, i))){
int size = res.size();
list.add(s.substring(start, i));
backtrack(res, list, i, set, s);
list.remove(list.size() - 1);
if (res.size() == size){
failed.add(i);
}
}
}
}
HashSet<Integer> failed = new HashSet<>();
}