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: []
简单的dfs，能work，但是复杂的case会time out
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> res = new ArrayList<>();
List<String> clist = new ArrayList<>();
Set<String> set = new HashSet<>(wordDict);
helper(s, set, res, clist, 0);
return res;
}
private void helper(String s, Set<String> set, List<String> res, List<String> clist, int start) {
if(start == s.length()){
res.add(convert(clist));
return;
}
for(int i = start; i < s.length(); i++) {
String t = s.substring(start, i+1);
if(set.contains(t)) {
clist.add(t);
helper(s, set, res, clist, i+1);
clist.remove(clist.size() - 1);
}
}
}
private String convert(List<String> clist) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < clist.size() - 1; i++) {
sb.append(clist.get(i) + " ");
}
sb.append(clist.get(clist.size() - 1));
return new String(sb);
}
}
这个方法的逐渐演化
https://leetcode.com/problems/word-break-ii/discuss/44359/Java-recursive-solution-evolution.
This problem looks very easy. First crack let's try simple recursion.
public class Solution {
public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> results = new ArrayList<String>();
_break(s, wordDict, new ArrayList<String>(), results);
return results;
}
private void _break(String s, Set<String> dict, List<String> count, List<String> results){
if (s.equals("")){
StringBuilder b = new StringBuilder();
for (int i=0;i<count.size();i++){
if (i>0 && i<count.size()){
b.append(" ");
}
b.append(count.get(i));
}
results.add(b.toString());
return;
}
for (int i=0;i<s.length();i++){
String sub = s.substring(0, i+1);
if (dict.contains(sub)){
count.add(sub);
_break(s.substring(i+1), dict, count, results);
count.remove(count.size()-1);
}
}
}
}
This passes all tests except TLE on last one. Let's add memoization on cases where we don't get a result (because it's easy to add)
public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> results = new ArrayList<String>();
_break(s, wordDict, new ArrayList<String>(), results);
return results;
}
private Set<String> fails = new HashSet<String>();
private boolean _break(String s, Set<String> dict, List<String> count, List<String> results){
if (s.equals("")){
StringBuilder b = new StringBuilder();
for (int i=0;i<count.size();i++){
if (i>0){
b.append(" ");
}
b.append(count.get(i));
}
results.add(b.toString());
return true;
}
boolean bAll = false;
for (int i=0;i<s.length();i++){
String sub = s.substring(0, i+1);
if (dict.contains(sub) && !(fails.contains(s.substring(i+1)))){
count.add(sub);
boolean b = _break(s.substring(i+1), dict, count, results);
if (b){
bAll = true;
}
else{
fails.add(s.substring(i+1));
}
count.remove(count.size()-1);
}
}
return bAll;
}
Now all test cases pass. But can we do better? Let's add memoization on successes. This is a little trickier as we will need to do a bunch of array copying
public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> r = new ArrayList<String>();
List<List<String>> lists = _break(s, wordDict, new ArrayList<String>(), 0);
for (List<String> list: lists){
StringBuilder b = new StringBuilder();
b.append(list.remove(0));
for (String val: list){
b.append(" ").append(val);
}
r.add(b.toString());
}
return r;
}
private Set<String> fails = new HashSet<String>();
private Map<String, List<List<String>>> sucs = new HashMap<String, List<List<String>>>();
private List<List<String>> _break(String s, Set<String> dict, List<String> count, int index){
List<List<String>> allList = new ArrayList<List<String>>();
if (s.substring(index).equals("")){
allList.add(new LinkedList<String>(count));
}
else {
String sucTest = s.substring(0,index);
if (sucs.containsKey(sucTest)){
List<List<String>> endings = sucs.get(sucTest);
for (List<String> l:endings){
List<String> l1 = new LinkedList<String>(count);
l1.addAll(l);
allList.add(l1);
}
}
else{
for (int i=index;i<s.length();i++){
String sub = s.substring(index, i+1);
String test = s.substring(i+1);
if (dict.contains(sub) && !(fails.contains(test))){
count.add(sub);
List<List<String>> l = _break(s, dict, count, i+1);
if(!l.isEmpty()){
allList.addAll(l);
List<List<String>> copyAll = new LinkedList<List<String>>();
for (List<String> l1:l){
List<String> copy = new LinkedList<String>(l1);
for (String ss:count){
copy.remove(ss);
}
copyAll.add(copy);
}
sucs.put(s.substring(0,i+1), copyAll);
}
else{
fails.add(test);
}
count.remove(count.size()-1);
}
}
}
}
return allList;
}