力扣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可以被拼接。文章来源:https://www.toymoban.com/news/detail-811038.html
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/
思路:处理字符串的排列组合还是回溯更好处理一些,本题采用回溯的方法进行处理,很简单的回溯模板。文章来源地址https://www.toymoban.com/news/detail-811038.html
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();
}
}
}
}
到了这里,关于力扣labuladong一刷day63天单词拆分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!