力扣labuladong一刷day63天单词拆分

本文主要是介绍力扣labuladong一刷day63天单词拆分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣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();}}}
}

这篇关于力扣labuladong一刷day63天单词拆分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---