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:
[]
- Method 1: MLE
- DP,将每一个字符位可能出现的结果都通过List保存起来，后面的结果是根据前面的结果而来的。
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String>[] dp = new List[s.length() + 1];
int len = s.length();
dp[0] = new ArrayList<>();
if(len == 0) return dp[0];
Set<Integer> set = new HashSet<>();
for(String ss : wordDict)
set.add(ss.length());
for(int i = 1; i <= len; i++){
dp[i] = new ArrayList<>();
for(Integer in : set){
if(i - in >= 0){
String sub = s.substring(i - in, i);
if(wordDict.contains(sub)){
List<String> tmp = dp[i - in];
if(i - in == 0)
dp[i].add(sub);
else{
for(String ss : tmp){
dp[i].add(ss + " " + sub);
}
}
}
}
}
}
return dp[len];
}
}- Method 2: dp + 递归
class Solution {
Map<String, List<String>> map = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
if(map.containsKey(s)) return map.get(s);
List<String> result = new ArrayList<>();
if(s.length() == 0){
result.add("");
map.put("", result);
return result;
}
for(String word : wordDict){
if(s.startsWith(word)){
List<String> subWords = wordBreak(s.substring(word.length()), wordDict);
for(String subWord : subWords)
result.add(word + (subWord.length() > 0 ? " ":"") + subWord);
}
}
map.put(s, result);
return result;
}
}- 通过回溯。 TLE
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> result = new LinkedList<>();
backtrace(s, wordDict, new StringBuilder(), result);
return result;
}
private void backtrace(String s, List<String> wordDict, StringBuilder sb, List<String> result){
if(sb.toString().replace(" ", "").length() == s.length())
result.add(sb.toString());
else{
String cur = sb.toString().replace(" ", "");
for(String ss : wordDict){
if(s.startsWith(cur + ss)){
StringBuilder temp = null;
if(cur.length() == 0)
temp = new StringBuilder(sb.toString() + ss);
else
temp = new StringBuilder(sb.toString() + " " + ss);
backtrace(s, wordDict, temp, result);
}
}
}
}
}- 通过DP， TLE
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> result = new LinkedList<>();
int len = s.length();
List[] dp = new List[len + 1];
dp[0] = new LinkedList<String>();
dp[0].add("");
for(int i = 1; i <= len; i++){
for(String word : wordDict){
int wordLen = word.length();
if(i - wordLen >= 0 && dp[i - wordLen] != null){
if(s.substring(i - wordLen, i).equals(word)){
if(dp[i] == null) dp[i] = new LinkedList<String>();
List<String> temp = dp[i - wordLen];
for(String ss : temp){
if(ss.length() == 0) dp[i].add(word);
else dp[i].add(ss + " " + word);
}
}
}
}
}
return dp[len];
}
}- DP + 递归， 思路是通后往前遍历。因为添加了递归，所以我们要用一个外部变量去保存dp，所以选择了map。这道题参考了一刷时候的结果。
class Solution {
Map<String, List<String>> map = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
if(map.containsKey(s)) return map.get(s);
List<String> result = new LinkedList<>();
if(s.length() == 0){
result.add("");
map.put("", result);
return result;
}
for(String word : wordDict){
if(s.startsWith(word)){
List<String> res = wordBreak(s.substring(word.length()), wordDict);
for(String ss : res){
result.add(word + (ss.length() == 0 ? "": " ") + ss);
}
}
}
map.put(s, result);
return result;
}
}- Method 1: reucrsion && dp
class Solution { Map<String, List<String>> map = new HashMap<>(); public List<String> wordBreak(String s, List<String> wordDict) { if(map.containsKey(s)) return map.get(s); if(s.length() == 0){ List<String> temp = new ArrayList<>(); temp.add(""); map.put("", temp); }else{ List<String> result = new ArrayList<>(); for(String word: wordDict){ if(s.startsWith(word)){ List<String> res = wordBreak(s.substring(word.length()), wordDict); for(String ss : res){ result.add(word + (ss.length() == 0 ? ss: " " + ss)); } } } map.put(s, result); } return map.get(s); } }
- Method 1: dp + recursion(bottom to top)
class Solution { private Map<String, List<String>> map = new HashMap<>(); // memory public List<String> wordBreak(String s, List<String> wordDict) { if(map.containsKey(s)) return map.get(s); else if(s.equals("")){ // break point List<String> temp = new ArrayList<>(); temp.add(""); map.put("", temp); return temp; }else{ List<String> result = new ArrayList<>(); for(String word: wordDict){ if(s.startsWith(word)){ List<String> res = wordBreak(s.substring(word.length()), wordDict); // Get result from sub question for(String ss : res){ result.add(word + (ss.length() == 0 ? "": " ") + ss); } } } map.put(s, result); return result; } } }