https://leetcode.cn/problems/word-break/description/
package 代码随想录.动态规划;
import java.util.HashSet;
import java.util.List;
public class _139单词拆分01 {
/**
*
* @param s 字符串 s
* @param wordDict 字符串列表 wordDict 作为字典
* @return 请你判断是否可以利用字典中出现的单词拼接出 s 。
*/
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<String>(wordDict);
boolean[] valid = new boolean[s.length() + 1];
valid[0] = true;
for (int i=1;i<= s.length();i++){
for (int j=0;j<i && !valid[i];j++){
if (set.contains(s.substring(j,i)) && valid[j]){
valid[i] = true;
}
}
}
return valid[s.length()];
}
}
package 代码随想录.动态规划;
import java.util.List;
public class _139单词拆分02 {
/**
*
* @param s
* @param wordDict
* @return
*/
public boolean wordBreak(String s, List<String> wordDict) {
boolean [] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i=1;i<=s.length();i++) {
for (String word : wordDict) {
int len = word.length();
if (i>=len && dp[i - len] && word.equals(s.substring(i-len,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
package 代码随想录.动态规划;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class _139单词拆分_回溯法and记忆法 {
private Set<String> sets;
private int [] memo;
/**
*
* @param s
* @param wordDict
* @return
*/
public boolean wordBreak(String s, List<String> wordDict) {
memo = new int[s.length()];
sets = new HashSet<String>(wordDict);
return backTrack(s,0);
}
/**
*
* @param s
* @param startIndex
* @return
*/
private boolean backTrack(String s, int startIndex) {
if (startIndex == s.length()){
return true;
}
if (memo[startIndex] == -1){
return false;
}
for (int i=startIndex;i<s.length();i++){
String subsets = s.substring(startIndex,i+1);
//拆分出来的单词无法匹配
if (!sets.contains(subsets)){
continue;
}
boolean res = backTrack(s,i+1);
if (res){
return true;
}
}
//这里是关键,找遍了startIndex~~s.length()也没能完全匹配
memo[startIndex] = -1;
return false;
}
}