力扣labuladong一刷day63天单词拆分
一、139. 单词拆分
题目链接：https://leetcode.cn/problems/word-break/description/
思路：s是否能被拆分成字典中的单词，单词数量是不限的，故是完全背包问题，不限数量的单词是否能组成字符串s，可以看的出来，并不是要求你长度相等就可以，还得有一定的顺序才能排列成字符串s，故本题还是一个排列问题。for循环的遍历顺序，背包在外物品在内是排列，物品在外背包在内是组合。
定义dp[i]表示，s[0, i]可以被字典元素拼出来，那么如果s[j, i]是字典元素，且dp[j]是true，就说明dp[i]可以被拼出。
故递推公式为 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < i && !dp[i]; j++) {
if (set.contains(s.substring(j, i)) && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.length()];
}
}
另外采用回溯的方法也可以做，不过要把遍历改为子问题，下面这个就是改造成分解子问题，当前片段存在字典中，只要后续的都可以拼接说明字符串s可以被拼接。
if (set.contains(s.substring(index, i+1))) {
boolean subProblem = dp(s,i+1);
}
class Solution {
Set<String> set;
int[] visited;
public boolean wordBreak(String s, List<String> wordDict) {
set = new HashSet<>(wordDict);
visited = new int[s.length()];
Arrays.fill(visited, -1);
return dp(s, 0);
}
boolean dp(String s, int index) {
if (index == s.length()) {
return true;
}
if (visited[index] != -1) {
return visited[index] != 0;
}
for (int i = index; i < s.length(); i++) {
if (set.contains(s.substring(index, i+1))) {
boolean subProblem = dp(s,i+1);
if (subProblem) {
visited[i] = 1;
return true;
}
}
}
visited[index] = 0;
return false;
}
}
二、140. 单词拆分 II
题目链接：https://leetcode.cn/problems/word-break-ii/description/
思路：处理字符串的排列组合还是回溯更好处理一些，本题采用回溯的方法进行处理，很简单的回溯模板。
class Solution {
LinkedList<String> track;
List<String> res;
List<String> wordDict;
public List<String> wordBreak(String s, List<String> wordDict) {
track = new LinkedList<>();
res = new LinkedList<>();
this.wordDict = wordDict;
dp(s, 0);
return res;
}
void dp(String s, int index) {
if (index == s.length()) {
res.add(String.join(" ", track));
return;
}
for (String word : wordDict) {
int len = word.length();
if (index + len <= s.length() && s.substring(index, index + len).equals(word)) {
track.addLast(word);
dp(s, index+len);
track.removeLast();
}
}
}
}
