[Leetcode] 140. Work Break II
1690 ワード
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, givens =
A solution is
これはやはりNPコースで、forサイクルにbacktrackingを追加しますが、これはタイムアウトします.
Return all such possible sentences.
For example, givens =
"catsanddog"
,dict = ["cat", "cats", "and", "sand", "dog"]
. A solution is
["cats and dog", "cat sand dog"]
. これはやはりNPコースで、forサイクルにbacktrackingを追加しますが、これはタイムアウトします.
import java.util.ArrayList;
public class Solution {
public List wordBreak(String s, Set dict) {
ArrayList result = new ArrayList();
if(s == null || s.length() == 0) return result;
ArrayList list = new ArrayList();
helper(s, dict, result, 0, list);
return result;
}
private void helper(String s, Set dict, ArrayList result, int start, ArrayList list){
if(start == s.length()){
StringBuffer sb = new StringBuffer();
for(int i = 0; i < list.size() - 1; i++){
sb.append(list.get(i) + " ");
}
sb.append(list.get(list.size() - 1));
result.add(sb.toString());
return;
}
for(int i = start; i < s.length(); i++){
String cur = s.substring(start, i + 1);
if(dict.contains(cur)){
list.add(cur);
helper(s, dict, result, i + 1, list);
list.remove(list.size() - 1);
}
}
}
}