佛山优化网站排名,虚拟主机和服务器有什么区别,沙洋县住房和城乡建设局网站,深圳彩页设计算法-动态规划/trie树-单词拆分
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/word-break/description/?envTypestudy-plan-v2envIdtop-interview-150
1.2 题目描述 2 动态规划
2.1 解题思路
dp[i]表示[0, i)字符串可否构建那么dp[i]可构建的条件是…算法-动态规划/trie树-单词拆分
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/word-break/description/?envTypestudy-plan-v2envIdtop-interview-150
1.2 题目描述 2 动态规划
2.1 解题思路
dp[i]表示[0, i)字符串可否构建那么dp[i]可构建的条件是[0,j)可构建且[j,i)包含在wordDict中这里你可能会问那如果是[j,i)不能直接构建而是有wordDict种的两个单词构建怎么办其实因为我们是从低到高构建的动态规划所以设k j 且 k i那么dp[k] true因为dp[j]true且 [j,k)在wordDict中。那么 [k, i)就是剩下的那个单词了所以 [j,i)也可以被构建。
2.2 代码
class Solution {public boolean wordBreak(String s, ListString wordDict) {// dp[i]表示[0, i)字符串可否构建// 那么dp[i]可构建的条件是[0,j)可构建且[j,i)包含在wordDict中boolean[] dp new boolean[s.length() 1];dp[0] true;SetString set new HashSet(wordDict);for (int i 1; i s.length(); i) {for (int j 0; j i; j) {if (dp[j] true set.contains(s.substring(j, i))) {dp[i] true;break;}}}return dp[s.length()];}
}2.3 时间复杂度
O(c*s.length)
2.4 空间复杂度
O( s.length)
3 trie树
3.1 解题思路
将wordDict构建trie树将s从位置0开始往后匹配查找如果当前位置能匹配上继续判断是否是单词结尾如果是且下一个单词开始的匹配也能成功就说明能构建返回true其他情况继续往后匹配
3.2 代码
class Solution {Trie root new Trie();// 记忆数组用来快速判定该位置是否可以作为单词结尾进行拆分构建boolean[] no new boolean[300];public boolean wordBreak(String s, ListString wordDict) {// 将所有word插入字典树for (String word : wordDict)root.insert(word);// 从0个字符开始往后查找只要匹配成功说明可以构建目标字符串if (root.find(s, 0)) {return true;}return false;}class Trie{public Trie[] children new Trie[26];// 当前child代表的字符是否是单词结尾boolean isEnd false;public void insert(String word) {if (null word || word.length() 0) {isEnd true;return;}int index word.charAt(0) - a;Trie child children[index];if (null child) {child new Trie();children[index] child;}child.insert(word.substring(1));}public boolean find(String s, int i) {// 快速判定当前字符位置是否可以拆分构建// 注意这里必须判定当前节点是否是root因为我们缓存是从根节点开始的// 否则会对其他child的正常判断过程造成误判if (this root no[i]) {return false;}char firstC s.charAt(i);Trie child children[firstC - a];if (null child) {// 如果不能匹配指定位置字符肯定不可构建if (this root) {no[i] true;}return false;}if (child.isEnd) {// 如果能找到目标字符且字符是单词结尾if (i 1 s.length()) {// 如果// 1.已经扫描到字符串最后的字符// 就说明当前位置可以用来拆分构建目标字符串return true;} else {if (root.find(s, i1)) {// 如果下一个字符往后的字符串能构建// 就说明当前位置可以用来拆分构建目标字符串return true;} else {// 否则说明i1字符虽是单词结尾但无法直接拆分构建记录下来no[i1] true;}}}if (i 1 s.length()) {// 还未到结尾可以继续往后查找return child.find(s, i1);} else {// 已到单词结尾构建失败return false;}}}
}3.3 时间复杂度 3.4 空间复杂度
O(s.length)
参考
循序渐进5种解法从字典树trie回溯延伸到动态规划
