算法-动态规划/trie树-单词拆分
算法-动态规划/trie树-单词拆分
1 题目概述
1.1 题目出处
https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-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, List<String> wordDict) {// dp[i]表示[0, i)字符串可否构建// 那么dp[i]可构建的条件是，[0,j)可构建且[j,i)包含在wordDict中boolean[] dp = new boolean[s.length() + 1];dp[0] = true;Set<String> 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, List<String> 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, i+1)) {// 如果下一个字符往后的字符串能构建// 就说明当前位置可以用来拆分构建目标字符串return true;} else {// 否则说明i+1字符虽是单词结尾，但无法直接拆分构建，记录下来no[i+1] = true;}}}if (i + 1 < s.length()) {// 还未到结尾，可以继续往后查找return child.find(s, i+1);} else {// 已到单词结尾，构建失败return false;}}}
}
3.3 时间复杂度
3.4 空间复杂度
O(s.length)
参考
- 循序渐进5种解法，从字典树trie回溯延伸到动态规划